How It Works

This chapter traces the classic sorting algorithms by hand on small arrays. After a quick look at three simple sorts, it walks through merge sort, quicksort and heapsort, the ones that matter most in practice and in interviews, and then counting sort, which never compares elements.

Three simple sorts

• Bubble sort: compare neighbors and swap them if they are out of order. Each pass "bubbles" the largest remaining value to the end. Stop early if a pass makes no swaps.
• Selection sort: find the smallest value in the unsorted part and swap it to the front. At most n - 1 swaps, but always about n²/2 comparisons.
• Insertion sort: insert the next element into its place in the sorted prefix, the way you arrange a hand of cards.

All three are O(n²) on average, but insertion sort is close to O(n) on nearly sorted input and very fast on tiny arrays, so real library sorts use it for short ranges. Here is insertion sort on [6, 3, 8, 2, 5]:

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:  # shift only strictly larger values: stable
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

print(insertion_sort([6, 3, 8, 2, 5]))  # [2, 3, 5, 6, 8]

Merge sort: split, then merge

Merge sort is the textbook divide-and-conquer algorithm. Split the array in half, sort each half recursively, then merge the two sorted halves. Merging repeatedly takes the smaller of the two front elements, so it costs time proportional to the total length. Sorting [38, 27, 43, 3, 9, 82, 10]:

In the final merge, 27 is compared with 3 and 3 is taken; then 27 against 9, 27 against 10, 27 against 82, and so on. Taking the left element on ties keeps the sort stable. The recursion is log n levels deep and each level merges n elements in total, giving O(n log n).

Quicksort: partition around a pivot

Quicksort picks a pivot, partitions the array so that smaller values go left and larger values go right, then sorts both sides recursively. There is no merge step, and the work happens in place. With the simple Lomuto partition and pivot 3 (the last element), [5, 2, 8, 1, 9, 3] is processed like this, where i is the next slot for a small value:

The pivot 3 now sits at its final index 2. Sorting [2, 1] and [5, 9, 8] the same way finishes the job.

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

data = [5, 2, 8, 1, 9, 3]
print(partition(data, 0, len(data) - 1), data)  # 2 [2, 1, 3, 5, 9, 8]

If the pivot is always an extreme value (for example, the last element of an already sorted array), the split is n - 1 versus 0 and the running time becomes O(n²). Real implementations pick a random pivot or the median of three.

Heapsort: extract from a max-heap

Heapsort turns the array into a max-heap (a complete binary tree where each parent is at least as large as its children), then repeatedly swaps the root, the maximum, to the end and repairs the heap. The children of index i are 2i + 1 and 2i + 2. [4, 10, 3, 5, 1] becomes the heap [10, 5, 3, 4, 1], and then:

Heapsort is O(n log n) in the worst case with O(1) extra memory, but it is not stable and its scattered memory access usually makes it slower than quicksort in practice.

Counting sort: count, then place

If the values are integers from 0 to k - 1, you can sort without comparisons. Count each value, turn the counts into prefix sums that mark where each value ends, then walk the input backwards and drop each element into place. Walking backwards makes it stable, which is what lets radix sort use it as a building block.

def counting_sort(a, k):
    count = [0] * k
    for x in a:
        count[x] += 1
    for v in range(1, k):
        count[v] += count[v - 1]  # prefix sum: one past the last slot of value v
    out = [0] * len(a)
    for x in reversed(a):
        count[x] -= 1
        out[count[x]] = x
    return out

print(counting_sort([3, 1, 2, 3, 0, 1], 4))  # [0, 1, 1, 2, 3, 3]

Radix sort applies this stable counting sort digit by digit, from the least significant to the most significant. Because each pass is stable, the order built by earlier passes survives.

Summary

• Insertion sort shines on tiny or nearly sorted arrays, which is why bigger algorithms use it internally.
• Merge sort splits and merges; taking the left element on ties keeps it stable.
• Quicksort partitions around a pivot, and pivot choice decides its performance.
• Heapsort is an in-place O(n log n) worst-case sort; counting sort sorts integers by counting instead of comparing.