Heap sort and counting sort take two very different routes to O(n log n)-or-better sorting. Heap sort gets there by reusing a data structure you may already know — the heap — as a sorting engine. Counting sort skips comparisons entirely, trading flexibility for raw speed when the data fits a specific shape.

Heap Sort: Build a Heap, Then Drain It

A heap is a tree-shaped structure where every parent is larger (max-heap) or smaller (min-heap) than its children — see heaps and priority queues for the full structure. Heap sort's trick: build a max-heap from the array, then repeatedly pull out the maximum element (the root) and place it at the end of the array, shrinking the heap by one each time.

import heapq

def heap_sort(arr):
    heap = arr[:]
    heapq.heapify(heap)  # Python's heapq is a min-heap
    return [heapq.heappop(heap) for _ in range(len(heap))]

print(heap_sort([38, 27, 43, 3, 9, 82, 10]))

Output:

[3, 9, 10, 27, 38, 43, 82]

Building the heap takes O(n), and each of the n extractions costs O(log n) to restore the heap property — giving a guaranteed O(n log n) overall, with no unlucky-input worst case the way quick sort has. Heap sort is also in-place (O(1) extra space when implemented array-style, sinking elements within the same array rather than using a separate structure) — a real advantage over merge sort's O(n) auxiliary space. The tradeoff is that heap sort isn't stable: equal elements can end up reordered, because extraction only tracks heap position, not original index.

Counting Sort: Skip Comparisons Entirely

Every algorithm discussed elsewhere in this course — bubble, insertion, merge, quick, heap — is a comparison sort: it decides ordering purely by comparing pairs of elements, and it's a proven mathematical fact that no comparison sort can beat O(n log n) in the worst case. Counting sort escapes that limit entirely by not comparing elements at all.

Instead, it counts how many times each distinct value appears, then uses those counts to place every element directly into its correct output position.

def counting_sort(arr, max_value):
    counts = [0] * (max_value + 1)
    for num in arr:
        counts[num] += 1

    result = []
    for value, count in enumerate(counts):
        result.extend([value] * count)
    return result

print(counting_sort([4, 2, 2, 8, 3, 3, 1], max_value=8))

Output:

[1, 2, 2, 3, 3, 4, 8]

When Counting Sort Wins — and When It Doesn't

Counting sort runs in O(n + k), where k is the range of possible input values. When k is small and comparable to n (sorting exam scores from 0-100, or ages, or single-digit grades), this comfortably beats O(n log n). But the moment k grows large relative to n — sorting arbitrary 64-bit integers, for instance — the counts array itself becomes enormous and the algorithm stops making sense; its O(n + k) complexity depends entirely on k staying small. It also only works on discrete values you can count (non-negative integers, or things easily mapped to them), not arbitrary comparable objects like strings sorted alphabetically without extra modification. In those cases, a comparison sort like merge sort remains the general-purpose answer.