Median-of-3 Hoare quicksort, switching to insertion sort for small ranges and * to heapsort once recursion gets too deep. Recurses on the smaller partition * and loops on the larger, so stack depth stays O(log n). */
| 112 | * to heapsort once recursion gets too deep. Recurses on the smaller partition |
| 113 | * and loops on the larger, so stack depth stays O(log n). */ |
| 114 | static void srt_introsort(char *base, size_t n, size_t size, CompareFunc comp, |
| 115 | void *tmp, void *pivot, int depth) { |
| 116 | while (n > SRT_ISORT_MAX) { |
| 117 | if (depth <= 0) { |
| 118 | srt_heapsort(base, n, size, comp, tmp); |
| 119 | return; |
| 120 | } |
| 121 | --depth; |
| 122 | |
| 123 | /* Order lo/mid/hi so base[lo] <= base[mid] <= base[hi]; base[mid] is the |
| 124 | * pivot and base[lo]/base[hi] act as sentinels (the scan loops need no |
| 125 | * bounds checks). */ |
| 126 | char *lo = base; |
| 127 | char *mid = base + (n / 2) * size; |
| 128 | char *hi = base + (n - 1) * size; |
| 129 | if (comp(mid, lo) < 0) { swap(mid, lo, size); } |
| 130 | if (comp(hi, lo) < 0) { swap(hi, lo, size); } |
| 131 | if (comp(hi, mid) < 0) { swap(hi, mid, size); } |
| 132 | memcpy(pivot, mid, size); |
| 133 | |
| 134 | size_t i = 0, j = n - 1; |
| 135 | for (;;) { |
| 136 | do { ++i; } while (comp(base + i * size, pivot) < 0); |
| 137 | do { --j; } while (comp(base + j * size, pivot) > 0); |
| 138 | if (i >= j) { |
| 139 | break; |
| 140 | } |
| 141 | swap(base + i * size, base + j * size, size); |
| 142 | } |
| 143 | |
| 144 | /* Partitions: [0, j] and [j+1, n). Recurse the smaller, loop the larger. */ |
| 145 | size_t left_n = j + 1; |
| 146 | size_t right_n = n - left_n; |
| 147 | if (left_n < right_n) { |
| 148 | srt_introsort(base, left_n, size, comp, tmp, pivot, depth); |
| 149 | base += left_n * size; |
| 150 | n = right_n; |
| 151 | } else { |
| 152 | srt_introsort(base + left_n * size, right_n, size, comp, tmp, pivot, depth); |
| 153 | n = left_n; |
| 154 | } |
| 155 | } |
| 156 | srt_isort(base, n, size, comp, tmp); |
| 157 | } |
| 158 | |
| 159 | |
| 160 | static void merge(void *base, size_t low, size_t mid, size_t high, size_t size, CompareFunc comp, void *temp) { |
no test coverage detected