- unsigned char *first = array; /* Beginning of array. */
- unsigned char *last = first + size * cnt; /* End of array. */
- unsigned char *pivot = last - size; /* Element used as pivot. */
- unsigned char *middle; /* Invariant: elements on left are <= pivot. */
- unsigned char *current;
-
- ASSERT (array != NULL);
- ASSERT (cnt > 1);
- ASSERT (size > 0);
- ASSERT (compare != NULL);
-
- /* Choose a random pivot. */
- swap (pivot, first + (random_ulong () % cnt) * size, size);
-
- /* Iterate through the array moving elements less than or equal
- to the pivot to the middle. */
- middle = array;
- for (current = first; current < last; current += size)
- if (compare (current, pivot, aux) <= 0)
- {
- swap (middle, current, size);
- middle += size;
- }
-
- return (middle - first) / size;
+ for (;;)
+ {
+ /* Set `max' to the index of the largest element among I
+ and its children (if any). */
+ size_t left = 2 * i;
+ size_t right = 2 * i + 1;
+ size_t max = i;
+ if (left <= cnt && do_compare (array, left, max, size, compare, aux) > 0)
+ max = left;
+ if (right <= cnt
+ && do_compare (array, right, max, size, compare, aux) > 0)
+ max = right;
+
+ /* If the maximum value is already in element I, we're
+ done. */
+ if (max == i)
+ break;
+
+ /* Swap and continue down the heap. */
+ do_swap (array, i, max, size);
+ i = max;
+ }