Sorting

Bubble, merge and quick sort, plus stability and what Python really uses.

Sorting puts items in order, and a great deal of computing depends on it: fast searching, deduplication, merging, and ranking. Understanding a few classic algorithms teaches ideas (divide and conquer, invariants) that reach far beyond sorting itself.

Simple sorts: O(n squared)

Bubble sort repeatedly swaps adjacent items that are out of order, so large values "bubble" to the end. Insertion sort grows a sorted prefix by inserting each new item into place, like sorting playing cards in your hand. Both are easy to write, and insertion sort is genuinely fast on tiny or nearly sorted inputs.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

print(insertion_sort([5, 2, 4, 6, 1, 3]))

[1, 2, 3, 4, 5, 6]

Merge sort: O(n log n)

Merge sort is divide and conquer: split the list in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front item. The list is halved log n times, and each level of merging does O(n) work, giving O(n log n) always, at the cost of O(n) extra memory.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

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

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

Quick sort

Pick a pivot, partition the items into smaller and larger, and recursively sort each side. Average time is O(n log n) and it sorts in place, which is why it is so popular. The worst case is O(n squared), for example when the pivot is always the smallest item; picking a random pivot makes that vanishingly unlikely.

import random

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = random.choice(a)
    less    = [x for x in a if x < pivot]
    equal   = [x for x in a if x == pivot]
    greater = [x for x in a if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

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

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

What you should actually use

In real code, call the built-in. Python's sorted() and list.sort() use Timsort, a hybrid of merge and insertion sort that is O(n log n) worst case and very fast on partially ordered data. Use key= to sort by a computed value and reverse=True for descending.

people = [("Ann", 31), ("Bob", 25), ("Cy", 31)]
print(sorted(people, key=lambda p: p[1]))
print(sorted(people, key=lambda p: (-p[1], p[0])))   # age desc, then name

[('Bob', 25), ('Ann', 31), ('Cy', 31)]
[('Ann', 31), ('Cy', 31), ('Bob', 25)]

Stability

A sort is stable if equal items keep their original relative order. In the first output above, Ann stays before Cy. Stability lets you sort by one field, then another, and keep the first ordering as a tiebreaker.

The lower bound

Any sort that works by comparing items needs at least about n log n comparisons in the worst case. Non-comparison sorts such as counting sort get O(n) only when values are small integers in a known range.

words = ["pear", "fig", "apple", "kiwi", "date"]
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'pear', 'apple']