Sorting IV: Heap Sort and Counting Sort

Where we are

Sorting means putting a list of items into order, usually smallest to largest. So far the sorts you have seen compare pairs of items and swap them around. This lesson covers two more sorts that take very different routes:

• Heap sort still compares items, but it organizes them inside a clever structure called a heap so it can always grab the next-smallest (or next-largest) item quickly. It sorts in O(n log n) time using essentially no extra memory.
• Counting sort does not compare items at all. It counts how many times each value appears and then rebuilds the list from those counts. When the values are small whole numbers, it runs in O(n + k) time, which can be faster than any comparison sort.

A quick vocabulary refresher, because we assume nothing:

• n is the number of items in the list.
• Big-O is a shorthand for how the running time grows as n grows. O(n) means the work grows in step with n; O(n log n) grows a bit faster; O(n^2) grows much faster. Smaller is better.
• log n (log base 2) is roughly “how many times you can halve n before reaching 1.” For a million items, log n is about 20. So O(n log n) is close to linear and far cheaper than O(n^2).
• In place means the algorithm rearranges the original list without allocating a second big list. It uses O(1) extra space, meaning a fixed small amount no matter how big n is.
• Stable means that two items with equal sort keys keep their original left-to-right order after sorting. This matters when items carry extra data you care about.

Part 1: Heap sort

What a heap is

A heap is a way of arranging items so that the smallest (or largest) is always easy to find. We will use a min-heap, where the rule is: every item is less than or equal to the items directly beneath it. That means the very smallest item always sits at the top.

You can picture a heap as a binary tree: a top item (the root), each item having up to two items hanging below it (its children). It is “complete,” meaning it fills in left to right with no gaps.

graph TD
    A["1 (root, smallest)"] --> B["3"]
    A --> C["2"]
    B --> D["7"]
    B --> E["8"]
    C --> F["5"]

Notice the rule holds everywhere: 1 is below nothing, and 3, 2, 7, 8, 5 are each greater than the item directly above them. The root is the minimum.

The trick: a tree stored in a plain list

We do not need real tree objects. A complete binary tree fits perfectly into a flat list using index arithmetic. If an item sits at index i:

• its left child is at index 2*i + 1
• its right child is at index 2*i + 2
• its parent is at index (i - 1) // 2 (where // is integer division, which divides and throws away the remainder: 7 // 2 -> 3)

So the tree above is just the list [1, 3, 2, 7, 8, 5]. Index 0 holds 1 (the root); its children are at indices 1 and 2, holding 3 and 2; and so on. This is why heap sort needs no extra memory: the “tree” lives inside the same list you are sorting.

Two operations we need

Sift down (also called “heapify at an index”): if an item is bigger than one of its children, it is in the wrong place. We swap it with its smaller child, then keep going down until it is correctly placed. This is how we repair the heap rule after a change.

Extract min: the smallest item is at index 0. To remove it, we swap it to the end of the list, shrink the heap by one, and sift the new root down to restore the rule. The removed minimum now sits in its final sorted position at the end.

The two phases of heap sort

1. Build the heap. Turn the raw list into a valid heap by sifting down every item that has children, starting from the last such item and moving toward the front. This costs O(n) time (a known result; most items are near the bottom and barely move).
2. Sort by repeated extraction. Repeatedly extract the minimum. Each extraction places one item into its correct final slot at the back of the list. Do this n times and the list is sorted. Each extraction costs O(log n) because sifting travels at most the height of the tree, which is log n. So this phase is O(n log n).

The extract phase loops the same few moves. Starting from the built min-heap, each round pulls the smallest off the top and parks it at the back, then repairs what is left:

flowchart TD
    S["Built min-heap: root = smallest"] --> A["Swap root with last item in the heap"]
    A --> B["Shrink heap size by 1 (last slot is now final and sorted)"]
    B --> C["Sift the new root down until the heap rule holds again"]
    C --> D{"Heap still has more than 1 item?"}
    D -- yes --> A
    D -- no --> E["Done: list is fully sorted"]

Note: extracting the minimum repeatedly and parking it at the back builds the list in descending order inside the array. To get the usual ascending order in place, heap sort normally uses a max-heap (largest on top) and parks the largest at the back each time. The mechanism is identical; only the comparison flips. We use a min-heap below because “smallest on top” is the easier picture, and we simply reverse at the end.

Heap sort in Python

def sift_down(a, start, size):
    # Repair the heap rooted at index `start`, considering only a[0:size].
    root = start
    while True:
        left = 2 * root + 1
        right = 2 * root + 2
        smallest = root
        if left < size and a[left] < a[smallest]:
            smallest = left
        if right < size and a[right] < a[smallest]:
            smallest = right
        if smallest == root:
            break                      # rule holds, nothing to do
        a[root], a[smallest] = a[smallest], a[root]  # swap down
        root = smallest

def heap_sort(a):
    n = len(a)
    # Phase 1: build the min-heap in place. O(n).
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)
    # Phase 2: repeatedly extract the min to the back. O(n log n).
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]    # smallest goes to the back
        sift_down(a, 0, end)           # restore heap on the shrunk part
    a.reverse()                        # min-heap parks descending; flip to ascending
    return a

print(heap_sort([4, 10, 3, 5, 1]))    # -> [1, 3, 4, 5, 10]

n // 2 - 1 is the index of the last item that has any children, so we start repairing there and work backward to the root.

Time is O(n log n) in the best, average, and worst case. Space is O(1): the swaps happen inside the original list, and the recursion is written as a loop so there is no growing call stack.

When heap sort is the right tool

• You want guaranteed O(n log n) with no risk of a slow worst case (quicksort can degrade to O(n^2); heap sort never does).
• Memory is tight and you cannot spare the extra O(n) that merge sort needs.
• You do not need stability. Heap sort is not stable; equal items can be reordered by the swaps.

Part 2: Counting sort

The idea

Every sort above compares items to each other. There is a proven floor: any sort that only compares pairs needs at least about n log n comparisons in the worst case. Counting sort sidesteps that floor by not comparing at all. Instead it uses the values themselves as positions.

Counting sort works only when the items are integers in a small known range, say 0 through k. The plan:

1. Make a count array of size k + 1, all zeros. Position v in this array will hold “how many times value v appears.”
2. Walk the input once and tally each value.
3. Walk the count array and write each value out the right number of times, smallest value first.

Two passes over the data, and not a single comparison between items:

flowchart LR
    A["Input list of small integers"] --> B["Tally each value into the count array"]
    B --> C["Walk count array low to high"]
    C --> D["Emit each value 'count' times"]
    D --> E["Sorted output"]

k is the size of the value range, not the number of items. If your values are 0 to 9, then k = 9 regardless of whether you have five items or five million.

Step-by-step trace

Sort [2, 5, 3, 0, 2, 3, 0, 3]. The values range from 0 to 5, so k = 5 and the count array has 6 slots (indices 0 through 5).

Phase A: build the count array. Start at all zeros, then add one for each value seen.

Final counts read: value 0 appears 2 times, 1 appears 0 times, 2 appears 2 times, 3 appears 3 times, 4 appears 0 times, 5 appears 1 time.

Phase B: rebuild the output. Walk the count array left to right and emit each value that many times.

The output is sorted, and we never compared two items to each other.

Counting sort in Python

The simple version above sorts plain numbers:

def counting_sort(a):
    if not a:
        return a
    k = max(a)                         # largest value; range is 0..k
    count = [0] * (k + 1)              # one slot per possible value
    for v in a:                        # Phase A: tally, O(n)
        count[v] += 1
    out = []
    for value in range(k + 1):         # Phase B: rebuild, O(n + k)
        out.extend([value] * count[value])
    return out

print(counting_sort([2, 5, 3, 0, 2, 3, 0, 3]))  # -> [0, 0, 2, 2, 3, 3, 3, 5]

Time is O(n + k): one pass over the n items to count, and one pass over the k + 1 slots to rebuild. Space is O(n + k): the count array is size k + 1 and the output is size n.

Making it stable (the version that carries data)

The rebuild above throws away the original items and reprints bare numbers, so stability is moot. But counting sort is genuinely useful when each item carries a key plus extra data, and you want equal keys to keep their input order. That stable form uses the count array to compute a starting position for each key, then places items from right to left:

def counting_sort_stable(pairs, k):
    # pairs is a list of (key, data); keys are integers in 0..k.
    count = [0] * (k + 1)
    for key, _ in pairs:
        count[key] += 1
    # Turn counts into starting positions (a prefix sum).
    start = 0
    for value in range(k + 1):
        count[value], start = start, start + count[value]
    out = [None] * len(pairs)
    for key, data in pairs:            # left to right keeps input order stable
        out[count[key]] = (key, data)
        count[key] += 1
    return out

data = [(2, "a"), (1, "b"), (2, "c"), (1, "d")]
print(counting_sort_stable(data, 2))
# -> [(1, 'b'), (1, 'd'), (2, 'a'), (2, 'c')]

The two 1s keep order b then d, and the two 2s keep a then c. That is stability.

When counting sort is the right tool

• The items are integers (or map cleanly to integers) in a range k that is not much larger than n.
• Examples: sorting ages (0 to 120), exam scores (0 to 100), letters (0 to 25), or grouping records by a small category id.
• Avoid it when k is huge. Sorting eight values that range up to a billion would build a billion-slot count array. The O(n + k) cost is dominated by k, and you would waste enormous memory for almost nothing.

A brief word on radix sort

What if the values are integers but the range k is large, like phone numbers or 32-bit ids? Radix sort handles that. It sorts the numbers one digit at a time, from the least significant digit to the most, running a stable counting sort on each digit pass. Each pass has only 10 possible values (digits 0 to 9), so k stays tiny. With d digits it runs in O(d * (n + 10)), effectively O(n) when the numbers have a fixed width. You do not need to implement it now; just know that radix sort is the standard way to extend counting sort to large integer ranges, and it depends entirely on counting sort being stable.

Big-O summary

Here k is the value range, d is the number of digits, and b is the base per digit (10 for decimal). For comparison: merge sort is O(n log n) time and O(n) space and stable; heap sort trades stability away to win back that space.

Why heap sort is O(n log n): the build phase is O(n), then n extractions each cost a sift-down that travels at most the tree height log n, giving n * log n.

Why counting sort is O(n + k): one full pass to tally the n items, one full pass across the k + 1 count slots to rebuild. No step repeats either loop.

Common pitfalls

• Counting sort on a wide range. If values can be up to a billion, count = [0] * (k + 1) allocates a billion slots and blows up memory. Check that k is comparable to n before choosing counting sort.
• Negative numbers in counting sort. Indexes start at 0, so a value of -3 cannot index the count array directly. Shift everything by the minimum first: use count[v - min_v] and add min_v back when rebuilding.
• Assuming heap sort is stable. It is not. If you must preserve the order of equal items, use a stable sort (merge sort, or Python’s built-in sorted, which is stable).
• Off-by-one in heap indices. The child of index i is 2*i + 1 and 2*i + 2, not 2*i and 2*i + 1. Getting this wrong silently corrupts the heap. Guard every child access with child < size.
• Confusing n and k. In O(n + k), n is the count of items and k is the size of the value range. They are different things; a small list with a huge value range is still slow.
• Reaching for these first. For everyday sorting, Python’s built-in sorted(list) is the right answer: it is O(n log n), stable, and highly optimized. Heap sort and counting sort are tools for specific constraints (tight memory, or small-integer keys), not defaults.

Practice

1. Trace counting sort by hand on [3, 1, 3, 0, 2, 1]. Write out the count array after every item is tallied, then write the rebuild table. Confirm your final list matches sorted([3, 1, 3, 0, 2, 1]).
2. Modify counting_sort so it also works when the input contains negative integers (for example [-2, 0, -2, 3, 1]). Hint: find min(a) and offset every index by it.
3. Add a print inside heap_sort’s extract loop that shows the list after each extraction, run it on [4, 10, 3, 5, 1], and check that one more item lands in its final position each round.