Sorting Algorithms II

Quick Sort

Pick a pivot value, then partition the rest of the list into everything smaller and everything larger. Recursively sort each side (the same recursive shape as Lesson 5 and Lesson 14's merge sort), and the whole list ends up sorted with no merge step needed, the pivot is already exactly where it belongs.

def quick_sort(items: list[int]) -> list[int]:
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    left = [x for x in items if x < pivot]
    middle = [x for x in items if x == pivot]
    right = [x for x in items if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([5, 3, 8, 1, 9, 2]))

[1, 2, 3, 5, 8, 9]

That version is easy to follow, but building three new lists at every call costs O(n) extra space per level. The classic in-place version instead partitions the list around itself using a partition helper, so only recursion-stack space is used:

def quick_sort_in_place(items: list[int], low: int = 0, high: int | None = None) -> list[int]:
    if high is None:
        high = len(items) - 1
    if low < high:
        pivot_index = partition(items, low, high)
        quick_sort_in_place(items, low, pivot_index - 1)
        quick_sort_in_place(items, pivot_index + 1, high)
    return items

def partition(items: list[int], low: int, high: int) -> int:
    pivot = items[high]
    i = low - 1
    for j in range(low, high):
        if items[j] <= pivot:
            i += 1
            items[i], items[j] = items[j], items[i]
    items[i + 1], items[high] = items[high], items[i + 1]
    return i + 1

print(quick_sort_in_place([5, 3, 8, 1, 9, 2]))

[1, 2, 3, 5, 8, 9]

Heap Sort

Lesson 9's heap always keeps its largest (or smallest) value at the root in O(1) time. Heap sort exploits that directly: turn the whole array into a max-heap, then repeatedly swap the root (the current maximum) with the last unsorted slot and sift the new root back into place. Each swap drops one more value into its final sorted position.

def heapify(items: list[int], n: int, root: int) -> None:
    while True:
        largest = root
        left = 2 * root + 1
        right = 2 * root + 2
        if left < n and items[left] > items[largest]:
            largest = left
        if right < n and items[right] > items[largest]:
            largest = right
        if largest == root:
            break                     # heap property restored, no need to go further
        items[root], items[largest] = items[largest], items[root]
        root = largest                # keep sifting down from the swapped-into position

def heap_sort(items: list[int]) -> list[int]:
    n = len(items)
    for root in range(n // 2 - 1, -1, -1):   # build a max-heap from the bottom up
        heapify(items, n, root)
    for end in range(n - 1, 0, -1):
        items[0], items[end] = items[end], items[0]   # move current max to its final slot
        heapify(items, end, 0)                          # restore heap order in the shrunken heap
    return items

print(heap_sort([5, 3, 8, 1, 9, 2]))

[1, 2, 3, 5, 8, 9]

Building the heap costs O(n), and each of the n extraction steps costs O(log n) to sift down, giving O(n log n) in the best, average, and worst case, unlike quick sort, heap sort's runtime doesn't depend on the input's initial order. It also sorts entirely in place, using only O(1) extra space, better than merge sort's O(n).

Counting Sort

Every algorithm so far decides order by comparing pairs of elements, and no comparison-based sort can beat O(n log n) in the worst case. Counting sort sidesteps the comparison entirely: if the values are integers within a known range, just count how many times each value appears, then write each value back out that many times, in order.

def counting_sort(items: list[int]) -> list[int]:
    if not items:
        return items
    minimum, maximum = min(items), max(items)
    counts = [0] * (maximum - minimum + 1)
    for value in items:
        counts[value - minimum] += 1     # tally how many times each value appears
    result = []
    for offset, count in enumerate(counts):
        result.extend([offset + minimum] * count)   # write each value back "count" times
    return result

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

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

This runs in O(n + k) time, where k is the range of values (maximum - minimum). That's faster than O(n log n) when k is small relative to n, but it falls apart for a huge range: sorting six numbers spread across a million possible values would allocate a million-slot counts array to save almost nothing.

Radix Sort

Radix sort handles that huge-range problem by never counting the whole value at once. Instead, it runs a counting sort on just one digit at a time, ones place first, then tens, then hundreds, and so on, using each pass's results as the input to the next.

def counting_sort_by_digit(items: list[int], exp: int) -> list[int]:
    n = len(items)
    output = [0] * n
    counts = [0] * 10
    for value in items:
        digit = (value // exp) % 10
        counts[digit] += 1
    for d in range(1, 10):
        counts[d] += counts[d - 1]       # running totals give each digit its final block
    for i in range(n - 1, -1, -1):       # walk backward so equal digits keep their order
        digit = (items[i] // exp) % 10
        counts[digit] -= 1
        output[counts[digit]] = items[i]
    return output

def radix_sort(items: list[int]) -> list[int]:
    if not items:
        return items
    maximum = max(items)
    exp = 1
    while maximum // exp > 0:
        items = counting_sort_by_digit(items, exp)
        exp *= 10
    return items

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

[2, 24, 45, 66, 75, 90, 170, 802]

One stable counting sort runs per digit, starting from the ones place. Each pass reorders the whole array by just that digit, and because every pass is stable, the ordering from earlier (less significant) digits survives as a tiebreaker:

With d digits in the largest number, radix sort runs in O(d · (n + k)) where k = 10 for each digit pass, effectively O(d · n). For fixed-width keys like 32-bit integers, d is a constant, making this linear in n, genuinely faster than any comparison-based sort can ever be.

Complexity at a Glance

k is the key range (counting sort) or the digit base of 10 (radix sort); d is the number of digits in the largest value. Quick sort's recursion-stack usage tracks its own partition balance: O(log n) when splits stay roughly even, but the exact same worst-case input that pushes its runtime to O(n²) (an already-sorted list with this last-element pivot) also pushes its stack depth to O(n), one recursive call per element. The in-place partition-swap version of quick sort shown here isn't stable, swapping elements across the pivot can reorder equal keys, but heap sort's sift-down swaps break stability too, both trade stability for speed and space that merge sort doesn't have to give up.