2.4Heap sort and non-comparison sorts
The idea
Heap sort builds a heap and repeatedly moves the maximum to the end. Counting, radix and bucket sort avoid comparisons altogether.
Think of it like this: Heap sort is a tournament that keeps crowning the champion; counting sort is a tally sheet.
Why it exists
These sorts show why Ω(n log n) is only a bound for comparison sorting.
How it works
- Heap sort: build a max-heap (O(n)), swap root with the last item, sift down, repeat.
- Counting sort: tally each value, prefix-sum the tallies, place items.
- Radix sort: stable counting sort on each digit, least significant first.
- Complexities: Θ(n log n), Θ(n + k), Θ(d(n + k)).
Worked example: Sort 1,000,000 numbers each below 1000
Counting sort: Θ(n + k) = about 1,001,000 steps. A comparison sort needs about 20,000,000.
Now play with it
- →Run heap sort on the default array and read the build then extraction phases.
- →Read the non-comparison table below it.
- Start: 4 10 3 5 1 8 2
- build max-heap: heapify node 2
- sift down: swap 3 below 8
- build max-heap: heapify node 1
- build max-heap: heapify node 0
- sift down: swap 4 below 10
- sift down: swap 4 below 5
- max-heap built: 10 5 8 4 1 3 2
- move max 10 to the end
- sift down: swap 2 below 8
- sift down: swap 2 below 3
- move max 8 to the end
- sift down: swap 2 below 5
- sift down: swap 2 below 4
- move max 5 to the end
- sift down: swap 1 below 4
- sift down: swap 1 below 2
- move max 4 to the end
- sift down: swap 1 below 3
- move max 3 to the end
- sift down: swap 1 below 2
- move max 2 to the end
- sorted
Θ(n log n) always, in place, not stable. Building the heap costs only O(n).
| Sort | Time | Condition |
|---|---|---|
| Counting sort | Θ(n + k) | integer keys in 0..k, stable |
| Radix sort | Θ(d(n + k)) | d digits, a stable sort per digit |
| Bucket sort | Θ(n) average | input spread uniformly over a range |
These beat n log n because they do not compare elements; the Ω(n log n) bound does not apply to them.
Check yourself
Counting sort on n integers in the range 0 to k runs in
Exam notes (the dense version)
Heap sort: build a max-heap in O(n), then extract n times: Θ(n log n) always, in place, not stable. Counting sort sorts n integers in range 0..k in Θ(n + k) and is stable. Radix sort sorts d-digit numbers with a stable pass per digit in Θ(d(n + k)). Bucket sort is O(n) on average for uniformly spread input.
Previous year questions: Sorting & Searching (9)
PYQs are grouped by topic, so this is the full set for Sorting & Searching; try the ones that match this subtopic. Open all 9 on the topic page.