Sift the element at index i down a max-heap of n elements. */
| 77 | |
| 78 | /* Sift the element at index i down a max-heap of n elements. */ |
| 79 | static void srt_siftdown(char *base, size_t i, size_t n, size_t size, CompareFunc comp, void *tmp) { |
| 80 | memcpy(tmp, base + i * size, size); |
| 81 | for (;;) { |
| 82 | size_t child = 2 * i + 1; |
| 83 | if (child >= n) { |
| 84 | break; |
| 85 | } |
| 86 | if (child + 1 < n && comp(base + child * size, base + (child + 1) * size) < 0) { |
| 87 | ++child; |
| 88 | } |
| 89 | if (comp(tmp, base + child * size) >= 0) { |
| 90 | break; |
| 91 | } |
| 92 | memcpy(base + i * size, base + child * size, size); |
| 93 | i = child; |
| 94 | } |
| 95 | memcpy(base + i * size, tmp, size); |
| 96 | } |
| 97 | |
| 98 | /* Heapsort — introsort's O(n log n) worst-case fallback. */ |
| 99 | static void srt_heapsort(char *base, size_t n, size_t size, CompareFunc comp, void *tmp) { |