Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Motivation
Mergesort has a good worst case of but needs extra arrays for merging. Heapsort has the same worst case and sorts in place.
Idea
Steps on A[1..n]:
- step 1: heapify
Ainto a maxheap, so the maximum is atA[1] - step 2: exchange
A[1]withA[n], which puts the maximum in its final place at the end - step 3: treat
A[1..n-1]as the new heap and siftdown from the root, which is the same as deleting the root - repeat steps 2 and 3 with
Example
Start with A = [3, 6, 10, 18, 8, 7, 25, 40]. Heapify gives [40, 18, 25, 6, 8, 7, 10, 3].

Swap with the last value , so is fixed at index 8. Siftdown on the first 7 cells gives [25, 18, 10, 6, 8, 7, 3 | 40]. The next round fixes at index 7, and so on.

Code
def heapsort(A): # A[1..n], A[0] unused
heapify(A)
for last in range(len(A) - 1, 1, -1):
A[1], A[last] = A[last], A[1] # max goes to the end
siftdown_range(A, 1, last - 1) # heap is now A[1..last-1]
def heapify(A):
n = len(A) - 1
for i in range(n // 2, 0, -1): # from index n/2 down to 1
siftdown_range(A, i, n)
def siftdown_range(A, i, n):
largest = i
l, r = 2 * i, 2 * i + 1
if l <= n and A[l] > A[largest]:
largest = l
if r <= n and A[r] > A[largest]:
largest = r
if largest != i:
A[i], A[largest] = A[largest], A[i]
siftdown_range(A, largest, n)Complexity
Heapify costs and each of the siftdowns costs :
| Algorithm | Worst case | Average case |
|---|---|---|
| Mergesort | ||
| Heapsort | ||
| Quicksort |