Heap Sort and Counting Sort

Analogy categoryAnalogies

Introduction

Heap sort and counting sort represent two different strategies for beating the pitfalls of quicksort and mergesort. Heap sort guarantees O(n log n) time in all cases while sorting in-place (unlike mergesort), by repeatedly extracting the maximum from a binary max-heap. Counting sort abandons comparisons altogether, achieving O(n+k) time by counting occurrences of each value, but only works well when the range of possible values (k) is small relative to n.

🏏

Cricket analogy: Heap sort is like a bowling captain repeatedly pulling the fastest bowler (the max) from a ranked bullpen to bowl the next over, guaranteeing consistent pace every match; counting sort instead just tallies how many players scored each specific run total, which only works fast if the range of scores is small.

Algorithm/Syntax

python

def heapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        heapify(arr, end, 0)
    return arr

Explanation

Heap sort has two phases: build a max-heap from the array in O(n) time (bottom-up heapify), then repeatedly swap the root (maximum) with the last unsorted element and sift down (heapify) the reduced heap, which takes O(log n) per extraction for n extractions, totaling O(n log n). Because it repeatedly swaps distant elements, heap sort is NOT stable, but it is in-place, using only O(1) extra space, making it attractive when memory is tight and worst-case guarantees matter. Counting sort instead builds a frequency array counting how many times each value appears (assuming values are integers in range [0, k]), then computes prefix sums to determine each element's final sorted position, producing a stable result in O(n + k) time and O(n + k) space.

🏏

Cricket analogy: Building the heap is like a selector doing one bottom-up pass to rank a squad by form (O(n)), then each over the captain swaps the star bowler to the front and re-settles the rest, an O(log n) reshuffle repeated for every player; counting sort instead just counts how many batters scored each run value and stacks them in order, keeping the original batting order for tied scores.

Example

python

def counting_sort(arr, max_val=None):
    if not arr:
        return arr
    k = max_val if max_val is not None else max(arr)
    count = [0] * (k + 1)
    for x in arr:
        count[x] += 1
    for i in range(1, k + 1):
        count[i] += count[i - 1]      # prefix sums -> final positions
    output = [0] * len(arr)
    for x in reversed(arr):           # iterate in reverse for stability
        count[x] -= 1
        output[count[x]] = x
    return output

# Trace: counting_sort([4, 2, 2, 8, 3, 3, 1])
# counts: idx 0..8 -> [0,1,2,2,1,0,0,0,1]
# prefix: [0,1,3,5,6,6,6,6,7]
# placing from the back yields stable order: [1, 2, 2, 3, 3, 4, 8]
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))  # [1, 2, 2, 3, 3, 4, 8]

Complexity

Heap sort: O(n log n) in ALL cases (best, average, worst), O(1) auxiliary space (in-place), NOT stable. Building the initial heap is O(n) (not O(n log n)) due to the amortized cost of heapify across levels; the n extraction+sift-down steps dominate at O(n log n). Counting sort: O(n + k) time and O(n + k) space where k is the range of input values; it is stable when implemented with the reverse-iteration placement shown above, but becomes inefficient (and memory-heavy) when k >> n, e.g. sorting sparse large-range integers.

🏏

Cricket analogy: Heap sort guarantees the same over-by-over pace (O(n log n)) no matter how the innings unfolds, using no extra dressing-room space, but the running order of tied scorers can shuffle; counting sort of run totals is instant when scores range 0-50 but becomes wasteful if one player scores 400 and everyone else scores under 10.

Key Takeaways

Heap sort: O(n log n) guaranteed, in-place O(1) space, NOT stable.
Counting sort: O(n+k) time, O(n+k) space, stable, only practical when k is not much larger than n.
Heap sort's max-heap build phase is O(n); extraction phase is O(n log n).
Counting sort is not comparison-based, so it can beat the O(n log n) comparison-sort lower bound.

Practice what you learned

1. What is the space complexity of heap sort?

2. Why is heap sort not stable?

3. What does the 'k' represent in counting sort's O(n+k) complexity?

4. When is counting sort a poor choice?

5. What is the time complexity of building the initial max-heap in heap sort?

Was this page helpful?

Quicksort and Mergesort

Binary Search

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#HeapSortAndCountingSort#Heap#Sort#Counting#Algorithm#Algorithms#StudyNotes#SkillVeris