How It Works

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.