Comparing Heapsort with Other Sorts

The questions in this section are about in-place heapsort, which sorts an array in ascending order in two phases.

buildHeap rearranges the array into a max-heap by sinking each internal node, from the last one back to the root. The children of index $i$ are at $2 i + 1$ and $2 i + 2$ .
sortdown repeatedly swaps the root with the last slot of the heap, shrinks the heap by one, and sinks the new root.

A sink swaps a value with its larger child, and it stops as soon as the value is no smaller than its larger child or has no children.

Exercise

Is heapsort stable? Support your answer by tracing heapsort on the array below, where 20a and 20b have the same key 20.

┌─────┬─────┬─────┐
│ 10  │ 20a │ 20b │
└─────┴─────┴─────┘

Solution

Heapsort is not stable.

start             [10, 20a, 20b]
after buildHeap   [20a, 10, 20b]    10 swaps with its larger child 20a (20b is not larger than 20a)
turn 1 swap       [20b, 10 | 20a]
turn 1 sink       [20b, 10 | 20a]   20b is no smaller than 10, so nothing moves
turn 2 swap       [10 | 20b, 20a]

The equal keys come out as 20b before 20a, the reverse of their input order.

Solution

It has worse cache locality. A sink jumps from index $i$ to $2 i + 1$ or $2 i + 2$ , so deep in a large heap each step lands far from the last one and misses the cache. Merge sort’s merge reads both halves from left to right and writes its output in order, so most of its reads are already in the cache.

Solution

Only heapsort.

Selection, insertion, and bubble sort are in-place, but they are $O (n^{2})$ .
Merge sort is $O (n lo g n)$ , but its merge needs an auxiliary array of size $O (n)$ . Merging in place avoids the array but gives up the $O (n lo g n)$ .