Heap Sort & Linear-Time Sorts — Data Structures Course

What you'll learn

Two ideas finish our tour of sorting: heap sort, an in-place O(n log n) sort built on a heap, and the linear-time sorts that break the O(n log n) barrier by not comparing elements at all.

By the end you'll be able to:

Describe how heap sort works (and where the heap comes from)
Explain why comparison sorts can't beat O(n log n)
Use counting, radix, and bucket sort — and know their limits

Heap sort

Heap sort turns the array into a max-heap (a tree where every parent ≥ its children), then repeatedly swaps the maximum (the root) to the end and shrinks the heap. Each extraction is O(log n), so the whole sort is O(n log n) — in place, with no extra array.

Note

Heap sort needs the heap data structure, which we build from scratch in Module 20. There you'll animate sift-up/sift-down and see exactly how extraction keeps the heap valid.

The O(n log n) barrier

Every sort so far works by comparing pairs of elements. It can be proven that any comparison-based sort must make at least ~n log n comparisons in the worst case — so O(n log n) is a hard floor for them. To go faster, you must stop comparing and instead use the values themselves as array indices.

Counting sort

If your values are integers in a small range 0..k, just count how many times each value appears, then read the counts back out in order. No comparisons — it's O(n + k):

Counting sort tallies each value

Counting sort — tally phase

1/8Counting sort. Input: 2, 5, 3, 0, 2, 3. Each index below is a possible value; each cell counts how many times it appears.

The index is the value; the cell is its count. Reading left to right yields sorted output.

Language

counting_sort.py

def counting_sort(a, k):        # values are in 0..k
    count = [0] * (k + 1)
    for x in a:
        count[x] += 1           # tally each value
    out = []
    for value in range(k + 1):
        out.extend([value] * count[value])   # emit in order
    return out

Watch out

Counting sort is only practical when k (the value range) is not much larger than n. To sort a handful of 64-bit integers, a count array of that range would be absurd — that's where radix sort comes in.

Radix & bucket sort

Radix sort sorts numbers one digit at a time (using a stable counting sort per digit), from least to most significant — O(d·(n + k)) for d digits. Bucket sort scatters values into buckets by range, sorts each bucket, then concatenates — O(n) on average for uniformly distributed data.

Choosing a sort

Sort	Time	Space	Stable?	Best for
`Heap sort`	O(n log n)	O(1)	No	Guaranteed bound, in place
`Merge sort`	O(n log n)	O(n)	Yes	Linked lists, stability
`Quick sort`	O(n log n) avg	O(log n)	No	General-purpose speed
`Counting`	O(n + k)	O(k)	Yes	Small integer range
`Radix`	O(d(n + k))	O(n + k)	Yes	Fixed-width integers/strings

Tip

In practice, most languages' built-in sort is a hybrid — e.g. Timsort (merge + insertion) in Python and Java, or introsort (quick + heap) in C++. You rarely write a sort yourself; you choose the right built-in and understand its guarantees.

Recap & quick check

Key takeaways

Heap sort is in-place O(n log n) using a max-heap (built in Module 20).
Comparison sorts cannot beat O(n log n) in the worst case.
Counting sort is O(n + k) — count values, then read them back in order.
Radix sort applies counting sort digit by digit for larger integer ranges.
Real-world sorts are hybrids: Timsort (Python/Java), introsort (C++).

Quick check

1. Why can't a comparison-based sort beat O(n log n)?

2. Counting sort runs in:

3. When is counting sort a poor choice?

4. Heap sort's main advantage over merge sort is:

That completes searching and sorting. Next we get O(1) average lookups with a completely different idea. Next up: Module 14 — Hash Tables & Hash Functions.