Sorting IV: Heap Sort and Counting Sort

Heap sort compares items inside a heap structure to sort in O(n log n) with no extra memory; counting sort skips comparisons entirely and runs in O(n + k) for small-integer values.

Vocabulary

• n: number of items. k: size of the value range (0..k), not the item count.
• In place: rearranges the original list, O(1) extra space.
• Stable: equal keys keep their original left-to-right order.
• log n (base 2): about how many times you halve n to reach 1 (~20 for a million).

Heap basics

• Heap: complete binary tree stored in a flat list. Min-heap rule: every item less than or equal to its children, so the smallest sits at index 0.
• Index arithmetic for item at index i:
  • left child: 2*i + 1
  • right child: 2*i + 2
  • parent: (i - 1) // 2
• List [1, 3, 2, 7, 8, 5] is the tree with root 1.

Heap sort

• Sift down: if an item exceeds a child, swap with the smaller child and keep going down until placed. Repairs the heap rule.
• Extract min: swap root to the end, shrink the heap by 1, sift new root down. Removed min lands in its final sorted slot at the back.
• Two phases:
  1. Build heap: sift down every item with children, from n // 2 - 1 back to index 0. O(n).
  2. Extract repeatedly: n extractions, each O(log n) sift. O(n log n).
• Min-heap parks items in descending order, then reverse to ascending (a max-heap would produce ascending directly).
• Time O(n log n) best/average/worst. Space O(1). Not stable.

extract loop:
  swap root <-> last item in heap
  shrink heap size by 1   (parked slot is final)
  sift new root down
  repeat while heap has > 1 item

Counting sort

• Works only for integers in a small known range 0..k. No comparisons.
  1. Count array of size k + 1, all zeros.
  2. One pass over input, tally each value.
  3. Walk count array low to high, emit each value count times.
• Time O(n + k), space O(n + k).
• Stable form: turn counts into starting positions (prefix sum), place items left to right so equal keys keep input order. Needed to carry data and to power radix sort.

Radix sort

• Extends counting sort to large integer ranges: sort one digit at a time, least significant first, running stable counting sort per digit.
• Each pass has base b values (10 for decimal), so k stays tiny. With d digits: O(d * (n + b)), effectively O(n) for fixed-width numbers. Depends on counting sort being stable.

Comparison

Gotchas

• Counting sort on a wide range: k up to a billion allocates a billion slots. Check k is comparable to n first.
• Negative values: index 0 cannot hold -3. Offset by min(a): use count[v - min_v], add min_v back.
• Heap sort is not stable. Use merge sort or sorted when equal-item order must survive.
• Heap child indices are 2*i + 1 and 2*i + 2, not 2*i and 2*i + 1. Guard every child with child < size.
• Do not confuse n (item count) with k (value range); a small list with a huge range is still slow.
• For everyday sorting, sorted(list) is the default: O(n log n), stable, optimized. These sorts are for tight memory or small-integer keys.