data-structures · advanced · ~40 min
Build a max-heap, then repeatedly extract the root into the back of the array.
Implement void heap_sort(int *a, size_t n) using an in-place binary max-heap.
Heap sort sorts in place with O(n log n) guaranteed and no recursion. Heaps also underpin priority queues, event schedulers, and OS process scheduling.
Array a of n ints.
a sorted in non-decreasing order, in place.
O(1) auxiliary memory. No malloc.
#include <stddef.h>
void heap_sort(int *a, size_t n) { /* TODO */ }
Off-by-one on parent/child index math; using i/2 when 0-indexed needs (i-1)/2; sifting up instead of down.
n==0, n==1, all-equal arrays, already-heap arrays.
O(n) build-heap, O(n log n) sort. O(1) memory.
Solve this exercise in the browser editor — compile and run against the test harness, no setup required.