Efficient sorting algorithms

Bubble sort needs about 5 · 10¹¹ comparisons to sort a million records — at 10⁸ comparisons per second that is well over an hour. Merge sort does the same job with about 2 · 10⁷ comparisons, in a fraction of a second. The difference is not the computer but the idea: divide and conquer. In this lesson we learn the two main n log n algorithms, the proof that comparison sorting cannot do better, and how to “cheat” that limit.

Merge sort

1. Divide: split the array into two halves.
2. Conquer: sort each half recursively (a one-element array is already sorted).
3. Combine: merge the two sorted halves by repeatedly moving the smaller front element to the output — linear time O(n).

comparisons = 0

def merge(left, right):
    global comparisons
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
comparisons = 0
merge_sort([(i * 37) % 1024 for i in range(1024)])
print('n = 1024:', comparisons, 'comparisons; n log2 n =', 1024 * 10)

[3, 9, 10, 27, 38, 43, 82]
n = 1024: 8161 comparisons; n log2 n = 10240

Quicksort

Quicksort does the work in the opposite order: first a pivot is chosen and the array is partitioned — elements less than or equal to the pivot go left, larger ones go right. The pivot lands in its final place, then both parts are sorted recursively; no merge is needed. It works in place (no extra array) and is very fast in practice, but it is not stable.

comparisons = 0

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

def quicksort(a, lo, hi):
    if lo < hi:
        p = partition(a, lo, hi)
        quicksort(a, lo, p - 1)
        quicksort(a, p + 1, hi)

a = [7, 2, 9, 4, 3, 8, 5]
print(partition(a, 0, 6), a)
for name, data in [('mixed', [(i * 37) % 200 for i in range(200)]), ('sorted', list(range(200)))]:
    comparisons = 0
    quicksort(data, 0, len(data) - 1)
    print(name, comparisons, data == sorted(data))

3 [2, 4, 3, 5, 9, 8, 7]
mixed 1542 True
sorted 19900 True

The lower bound: Ω(n log n)

Picture any sorting algorithm that only asks “is a ≤ b?” as a decision tree: each internal node is one comparison and each leaf is one answer — an ordering of the elements. n distinct elements can be ordered in n! ways, and each must lead to a different leaf. A binary tree of height h has at most 2ʰ leaves, so 2ʰ ≥ n!.

Counting sort: beating the bound

The Ω(n log n) bound applies only to comparison-based algorithms. If the keys are integers in the range 0 … k, counting sort makes no comparisons at all: it counts how often each value occurs, then writes the values out in order as many times as counted. Time and memory are O(n + k). Repeating a stable counting sort digit by digit is radix sort: O(d · (n + k)) for d-digit numbers.

import math

def counting_sort(a, k):
    count = [0] * (k + 1)
    for x in a:
        count[x] += 1
    out = []
    for value, c in enumerate(count):
        out.extend([value] * c)
    return count, out

print(counting_sort([2, 5, 3, 0, 2, 3, 0, 3], 5))
for n in [3, 4, 5, 10, 1000]:
    print(n, math.ceil(math.log2(math.factorial(n))))

([2, 0, 2, 3, 0, 1], [0, 0, 2, 2, 3, 3, 3, 5])
3 3
4 5
5 7
10 22
1000 8530