Heap Sort & Linear-Time Sorts

What you'll learn

One more comparison sort — heap sort — guarantees O(n log n) with O(1) extra space. Then we cheat: counting, radix, and bucket sort avoid comparisons entirely and run in linear time when the data cooperates.

By the end you'll be able to:

• Explain how heap sort uses a heap to sort in place
• State why comparison sorts can't beat Ω(n log n)
• Use counting, radix, and bucket sort — and know their limits

Heap sort

Treat the array as a binary max-heap: build it so the largest element is at the front, then repeatedly swap that max to the end and sift the heap back into shape over the shrinking front. The sorted region grows from the right:

def heap_sort(a):
    n = len(a)
    def sift_down(lo, hi):
        root = lo
        while 2 * root + 1 <= hi:
            child = 2 * root + 1
            if child + 1 <= hi and a[child] < a[child + 1]:
                child += 1
            if a[root] < a[child]:
                a[root], a[child] = a[child], a[root]
                root = child
            else:
                break
    for i in range(n // 2 - 1, -1, -1):   # build max-heap
        sift_down(i, n - 1)
    for hi in range(n - 1, 0, -1):        # extract max
        a[0], a[hi] = a[hi], a[0]
        sift_down(0, hi - 1)
    return a

The comparison barrier

Any sort that only compares elements must make at least Ω(n log n) comparisons in the worst case. The reason: there are n! possible orderings, and each comparison (a yes/no) can at best halve the possibilities, so you need log₂(n!) ≈ n log n comparisons to pin down the right one.

Counting sort

If the values are small integers in a known range 0..k, don't compare — tally. Count how many times each value appears, then read the counts back out in order. It's O(n + k):

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

Radix & bucket sort

• Radix sort sorts numbers (or fixed-length strings) digit by digit, using a stable counting sort on each digit from least to most significant. It's O(d·(n + b)) for d digits in base b.
• Bucket sort scatters values into buckets by range, sorts each bucket (often with insertion sort), then concatenates. It's O(n) on average for uniformly distributed data.

Choosing a sort

Recap & quick check

Sorting fully arranges data — but often you only need one element, like the median. That's faster. Next up: Module 10 — Selection & Order Statistics.