In-Place and Stable?

In the quadratic sorting chapter, we checked each algorithm for two properties besides its running time: whether it is in-place and whether it is stable.

In-place

Recall that a sort works in place when it needs only $O(1)$ auxiliary space on top of the array it is sorting: a fixed number of variables, and no second structure that grows with the input.

Heapsort is in-place. buildHeap and sortdown only swap elements within the input array. The only extra memory is a few index variables and the single temporary variable inside swap. Nothing grows with $n$, so heapsort uses $O(1)$ auxiliary space.

Heapsort is the first sort we have seen that is both $O(n\log n)$ and in-place. The $O(n^2)$ sorts (selection, insertion, bubble) are in-place but slow. Merge sort is $O(n\log n)$, but its merge needs an auxiliary array, and the in-place merge from the merge sort chapter is no longer $O(n\log n)$.

Stable

Recall that a sort is stable when elements that compare equal keep their original relative order.

Heapsort is not stable, for the reason the quadratic sorting chapter gave for selection sort: a swap between two slots that sit far apart can move one element past another equal to it, which reverses their order. Heapsort makes swaps like that. Both of its phases swap a node with one of its children, and a child can sit far from its parent in the array. sortdown also swaps the root with the last slot of the heap.

Take three items, two of them sharing the key 3. Write them 3a and 3b, with 3a first:

┌────┬────┬────┐
│ 3a │  1 │ 3b │
└────┴────┴────┘

buildHeap finds 3a already at least as large as its children, so it changes nothing. Then sortdown begins by swapping the root with the last slot of the heap (index 0 with index 2). That swap trades 3a and 3b:

┌────┬────┬────┐
│ 3b │  1 │ 3a │
└────┴────┴────┘

The last swap trades 3b and 1, and the array comes out:

┌────┬────┬────┐
│  1 │ 3b │ 3a │
└────┴────┴────┘

The two equal items end up 3b before 3a, the reverse of how they went in.