# Heap sort optimization

I tried to optimize heap sort algorithm. Instead of recursion, I used iteration:

void max_heapify (int arr[], int heapsize, int i) {
int left = 2 * i;
int right = 2 * i + 1;
int largest = i;
do {
if (i != largest) {
int tmp = arr[i];
arr[i] = arr[largest];
arr[largest] = tmp;
i = largest;
left = 2 * i;
right = 2 * i + 1;
}
if (left < heapsize && arr[largest] < arr[left])
largest = left;
if (right < heapsize && arr[largest] < arr[right])
largest = right;
} while (i != largest);
}

void heap_sort (int arr[], int size) {
int i;
for (i = size / 2 - 1; i >= 0; i--)
max_heapify(arr, size, i);
for (i = size - 1; i > 0; i--) {
int tmp = arr[i];
arr[i] = arr[0];
arr[0] = tmp;
max_heapify (arr, i, 0);
}
}


Seems like it's ok, but is there way to improve it?

• (Can you point me to reference material on recursive heapsort?) Commented Dec 30, 2023 at 18:55
• @greybeard here's one Commented Dec 30, 2023 at 19:39

1. Use size_t for element-counts, as that's what it is for. An int can be negative, and its range might be too small.

2. Signed overflow is UB. Avoid at all costs.

3. You needlessly duplicate the calculation for left and right child.

4. Because you don't want to exit out of the middle of the loop, you have to duplicate the condition, which is worse.

5. If a function is only for use inside a TU, mark it static so it cannot interfere with other TUs, and to promote inlining.

6. Minimize the scope of variables to enhance comprehension. Let the compiler worry about optimizing lifetimes.

7. Extract a swap-function.

static void swap(int arr[], size_t a, size_t b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}

static void max_heapify(int arr[], size_t size, size_t i) {
for (;;) {
size_t old = i;
size_t left = i * 2;
size_t right = i * 2 + 1;
if (right < size && arr[i] < arr[right])
i = right;
if (left < size && arr[i] < arr[left])
i = left;
if (old > SIZE_MAX / 2 || old == i)
return;
swap(arr, old, i);
}
}

void heap_sort (int arr[], size_t size) {
if (!size)
return;
for (size_t i = size / 2; i--;)
max_heapify(arr, size, i);
while (--size) {
swap(arr, size, 0);
max_heapify (arr, size, 0);
}
}

• (size_t)-1 more clear as SIZE_MAX. Commented Dec 30, 2023 at 3:57

One way to improve this is by taking out all the swaps and replacing them by moves.

What really happens in a "heapify" operation is that one element travels down some path through the (implicit) tree, while the other elements on that path travel up by one. You can implement that with swaps, but then it's always the same element that's getting swapped down, while the other elements on the path downwards take turns being the other element that's being swapped. This means that the original element (the one being heapified) is written into the array a bunch of times.

Alternatively, you can put that original element (the one that's being heapified) to the side leaving a "hole", then you can have the "hole" travel down the same path (this only takes one load and store, instead of the 2 loads and 2 stores that a swap costs) and finally when the path ends you can write the original element into the hole. The other elements along the path are stilled loaded and stored the same as before, but instead of loading and storing the original element a bunch of times, it is only loaded once at the start and stored once at the end.