Why order matters
Finding a word in a printed dictionary of a hundred thousand entries takes you a few seconds. Finding the same word in a pile of a hundred thousand unsorted index cards could take all afternoon. The difference is not the reader; it is that the dictionary is sorted, so every glance at a page tells you which way to go.
Computers exploit the same fact constantly. Databases keep their indexes in sorted order so that a lookup among billions of rows touches only a handful of them. Many problems become easy once the data is sorted: finding duplicates (they end up next to each other), the median (it's in the middle), the closest pair of numbers (they're neighbours), or grouping records (equal keys are together). Sorting is one of the most-studied problems in computer science, and the ideas invented for it, such as invariants, divide and conquer, randomisation and lower bounds, reach far beyond it.
This lesson builds on Measuring the cost of a program and Recursion and divide and conquer. The same algorithms are studied from the mathematician's side, with machine-checked proofs, in Lumenary Math's Algorithms, correctness and efficiency; here the emphasis is on the code and on how sorting is done in practice.
Linear and binary search
Linear search checks the items one by one. It works on any list, sorted or not, and costs comparisons in the worst case. Python's x in xs and xs.index(x) are linear searches.
Binary search needs a sorted list and is dramatically faster. Keep a range of positions where the target could still be. Look at the middle item of the range: if it is smaller than the target, the target can only be to its right; otherwise it can only be at the middle or to its left. Each comparison halves the range.
Binary search is famously easy to get almost right: off-by-one errors in the bounds, loops that never end when the range has two items. The safest way to write it is to state precisely what the variables mean, and to keep that statement true. The version below uses a half-open range [lo, hi), meaning positions lo up to but not including hi, the same convention as range and slices.
def binary_search(a, target):
"""Return the first index i with a[i] >= target (len(a) if there is none).
a must be sorted in non-decreasing order."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return loIt returns the position where target would be inserted to keep the list sorted; the target is present exactly when that position holds it. This is what Python's standard bisect.bisect_left computes.
Definition— loop invariant
A loop invariant is a statement about the program's variables that is true before the loop starts and is kept true by every iteration. When the loop ends, the invariant, combined with the reason the loop stopped, gives the result you want.
Theorem— binary search is correct
If a is sorted, binary_search(a, target) terminates after at most iterations (for ) and returns the smallest index with , or if there is none.
Proof
Invariant: every item before position lo is less than , and every item at position hi or later is at least ; and .
Initially lo = 0 and hi = n, so both parts speak about no items at all and hold trivially.
Each iteration keeps it. Since lo < hi, the midpoint satisfies lo ≤ mid < hi. If , then because the list is sorted, every with satisfies , so setting lo = mid + 1 keeps the first part true. Otherwise , and every with satisfies , so setting hi = mid keeps the second part true. This is the only place sortedness is used.
Termination. The length hi - lo is a natural number, and it strictly decreases, because mid + 1 > lo and mid < hi. Each iteration in fact leaves at most half of it, which gives the bound of iterations.
Result. The loop stops when lo == hi. By the invariant, everything before lo is less than and everything from lo on is at least , so lo is the smallest index with , or if no such item exists.
∎
A million items need at most 20 iterations; a billion, at most 30. One historical warning: in languages with fixed-size integers, such as Java or C, computing (lo + hi) / 2 can overflow when the list is huge. Joshua Bloch reported in 2006 that this bug had sat for years in Java's standard library; the safe form is lo + (hi - lo) / 2. Python's integers never overflow, so the problem doesn't arise here, but the lesson about reasoning carefully does.
import bisect
def linear_search(a, target):
steps = 0
for i in range(len(a)):
steps += 1
if a[i] == target:
return i, steps
return -1, steps
def binary_search(a, target):
lo, hi, steps = 0, len(a), 0
while lo < hi:
steps += 1
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
found = lo if lo < len(a) and a[lo] == target else -1
return found, steps
a = list(range(0, 2_000_000, 2)) # a million even numbers, sorted
for target in [0, 1_234_566, 1_999_998, 7]:
print(f"target {target:>9}: linear {linear_search(a, target)}, "
f"binary {binary_search(a, target)}, bisect_left {bisect.bisect_left(a, target)}")(The pairs show the index found, or −1, and the number of steps.)
Two simple sorts
Selection sort repeatedly selects the smallest remaining item and swaps it into place. Its invariant: after passes, positions to hold the smallest items, in order.
def selection_sort(a):
n = len(a)
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
if a[j] < a[smallest]:
smallest = j
a[i], a[smallest] = a[smallest], a[i]It always makes exactly comparisons, whatever the input, so it is in every case; its one virtue is that it makes at most swaps.
Insertion sort is how many people sort a hand of cards: take the next card and slide it left past every larger card. Its invariant: after processing position , the first items are the original first items, in sorted order.
def insertion_sort(a):
for i in range(1, len(a)):
x = a[i]
j = i - 1
while j >= 0 and a[j] > x: # shift larger items one place right
a[j + 1] = a[j]
j -= 1
a[j + 1] = xIts cost depends heavily on the input. On a sorted list, the inner loop never runs: comparisons, . On a reversed list, item shifts past all before it: shifts, . In general the number of shifts equals the number of inversions, pairs of items that are in the wrong order, so insertion sort is fast exactly when the data is nearly sorted. That, together with its tiny constant factors, is why real sorting libraries use it for short stretches of data.
Merge sort
Merge sort, described by John von Neumann in 1945, is divide and conquer in its purest form: split the list in half, sort each half recursively, and merge the two sorted halves. Merging is the clever part, and it is simple: repeatedly compare the front items of the two halves and move the smaller one to the output. Each comparison outputs one item, so merging a total of items takes at most comparisons.
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if right[j] < left[i]:
out.append(right[j]); j += 1
else: # on a tie, take from the left: keeps the sort stable
out.append(left[i]); i += 1
out.extend(left[i:])
out.extend(right[j:])
return out
def merge_sort(a):
if len(a) <= 1:
return list(a)
mid = len(a) // 2
return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))The running time satisfies , which the master theorem of the last lesson solves as , in every case. The price is memory: the merges build new lists, using extra space.
Quicksort
Quicksort, invented by Tony Hoare in 1959 and published in 1961–62, divides differently. Choose an item, the pivot; partition the others into those smaller than the pivot and the rest; then sort the two parts recursively. No merge step is needed: once the parts are sorted, smaller part, pivot, larger part is sorted.
def quicksort(a):
if len(a) <= 1:
return list(a)
pivot = a[0] # the simplest choice; see below
smaller = [x for x in a[1:] if x < pivot]
larger = [x for x in a[1:] if x >= pivot]
return quicksort(smaller) + [pivot] + quicksort(larger)Partitioning costs . If the pivot splits the list roughly in half each time, . But if the pivot is always the smallest or largest item, one part is empty and the other has items: . With "first item as pivot", that worst case happens on input that is already sorted, which is embarrassingly common in real data.
The standard cure is to choose the pivot at random. Then for every input, the expected number of comparisons is about ; the worst case is still possible but astronomically unlikely. You'll see the proof in Randomized algorithms.
The version above is written for clarity. Production quicksorts partition in place, swapping items within the array, so they need only extra memory for the recursion (if they recurse into the smaller part and loop on the larger), and their sequential memory access is very friendly to caches. Many C++ standard libraries use introsort, a quicksort that switches to heapsort if the recursion gets suspiciously deep, guaranteeing ; Java sorts arrays of numbers with a dual-pivot quicksort.
The program below counts comparisons for insertion sort, merge sort and quicksort with the two pivot rules, on random data and on already-sorted data.
import math
import random
comparisons = 0
def less(x, y):
global comparisons
comparisons += 1
return x < y
def insertion_sort(a):
a = list(a)
for i in range(1, len(a)):
x, j = a[i], i - 1
while j >= 0 and less(x, a[j]):
a[j + 1] = a[j]
j -= 1
a[j + 1] = x
return a
def merge_sort(a):
if len(a) <= 1:
return list(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 less(right[j], left[i]):
out.append(right[j]); j += 1
else:
out.append(left[i]); i += 1
return out + left[i:] + right[j:]
rng = random.Random(2026)
def first_index(n):
return 0
def random_index(n):
return rng.randrange(n)
def quicksort(a, choose):
if len(a) <= 1:
return list(a)
k = choose(len(a))
pivot, smaller, larger = a[k], [], []
for i, x in enumerate(a):
if i != k:
(smaller if less(x, pivot) else larger).append(x)
return quicksort(smaller, choose) + [pivot] + quicksort(larger, choose)
def count(sort, data, *extra):
global comparisons
comparisons = 0
assert sort(data, *extra) == sorted(data)
return comparisons
random_data = [rng.random() for _ in range(1000)]
sorted_data = list(range(300)) # kept small: the bad case recurses 300 deep
print(f"{'':28}{'random, n=1000':>16}{'sorted, n=300':>15}")
for name, sort, extra in [("insertion sort", insertion_sort, ()),
("merge sort", merge_sort, ()),
("quicksort, first pivot", quicksort, (first_index,)),
("quicksort, random pivot", quicksort, (random_index,))]:
print(f"{name:28}{count(sort, random_data, *extra):>16}{count(sort, sorted_data, *extra):>15}")
print(f"{'n log2 n for reference':28}{1000 * math.log2(1000):>16.0f}{300 * math.log2(300):>15.0f}")The n log n barrier
Merge sort makes about comparisons. Could a cleverer algorithm do substantially better? Not if it learns about the data only by comparing items, as every algorithm so far does.
Theorem— the comparison-sorting lower bound
Every algorithm that sorts distinct items using only comparisons between them makes at least comparisons on some input, and .
Proof
(Sketch.) Fix and an algorithm. Its behaviour on inputs of size can be drawn as a decision tree, like the one above: each node is a comparison, the two branches are its outcomes, and each leaf is where the algorithm stops, having determined the order. Different orderings of the input must reach different leaves, since they need different rearrangements, so the tree has at least leaves. A binary tree of height has at most leaves, so , that is . The height is the worst-case number of comparisons. Finally, the largest factors of are each at least , so and ; and gives the matching upper bound.
∎
So merge sort is asymptotically optimal among comparison sorts, and no amount of cleverness will beat by more than a constant factor. (A similar argument shows the average number of comparisons is also .) The bound has a loophole, though: it says nothing about algorithms that do more than compare. We'll use that loophole below.
Stability, keys, and Python's own sort
Definition— stable sort
A sort is stable if items with equal keys keep their original relative order.
Stability matters when you sort records by one field and want ties to keep an earlier order. Insertion sort and merge sort (taking from the left on ties) are stable; selection sort and in-place quicksort are not. Python's sorted and list.sort are guaranteed stable, which gives a neat technique for sorting by several keys: sort by the least important key first, then by the more important ones.
Both take a key argument: a function applied to each item, whose results are compared instead of the items. A lambda writes a small function in place: lambda s: s[1] is a function that takes s and returns s[1]. Tuples compare item by item, so a key returning a tuple sorts by several fields at once.
students = [("Amara", 88), ("Bao", 92), ("Chidi", 88), ("Dana", 75), ("Elif", 92), ("Femi", 75)]
by_mark = sorted(students, key=lambda s: s[1], reverse=True)
print(by_mark) # ties keep their alphabetical order: the sort is stable
by_mark_then_name = sorted(students, key=lambda s: (-s[1], s[0]))
print(by_mark_then_name) # one sort with a tuple key does the same job
words = ["banana", "Cherry", "apple", "date", "Elderberry", "fig"]
print(sorted(words)) # capitals first: 'C' and 'E' come before 'a'
print(sorted(words, key=str.lower)) # case-insensitive
print(sorted(words, key=len)) # by length; equal lengths keep their orderTimsort
Which algorithm does Python use? Since 2002 (Python 2.3), CPython has used Timsort, designed by Tim Peters and described in his notes listsort.txt. It is a stable merge sort built to exploit the order that real data often already has:
- It scans for runs: stretches that are already ascending, or strictly descending (which it reverses). Short runs are extended to a minimum length with binary insertion sort, which is fast on short lists.
- It merges runs, choosing which neighbouring runs to merge so that merges stay balanced. Since Python 3.11, that choice follows the "powersort" strategy of Munro and Wild.
- During a merge, if one run keeps winning, it switches to galloping: an exponential then binary search for how far ahead it can copy in one go.
The result is in the worst case and on data that is already sorted, or made of a few sorted pieces. Timsort has since been adopted well beyond Python, for example for sorting objects in Java and for Array.prototype.sort in the V8 JavaScript engine.
Beating n log n: counting sort
Suppose you must sort a million exam marks, each a whole number from 0 to 100. Instead of comparing marks, count them: make a list of 101 counters, go through the marks once adding 1 to counts[m], then output each mark as many times as it was counted. That is time for items with keys in a range of size : linear when is small. It doesn't contradict the lower bound, because it never compares two items; it uses each key as a list index.
To sort records by a small integer key (students by mark, say) and keep it stable, turn the counts into starting positions with running totals, then place each record at its key's next free position, going through the input in order. Counting sort is also the engine of radix sort, which sorts large numbers digit by digit, least significant digit first, relying on each pass being stable.
import random
import time
def counting_sort(marks, max_mark):
counts = [0] * (max_mark + 1)
for m in marks:
counts[m] += 1
result = []
for mark, c in enumerate(counts):
result.extend([mark] * c)
return result
rng = random.Random(7)
marks = [rng.randint(0, 100) for _ in range(200_000)]
t0 = time.perf_counter()
a = counting_sort(marks, 100)
t1 = time.perf_counter()
b = sorted(marks)
t2 = time.perf_counter()
assert a == b
print(f"counting sort (Python): {(t1 - t0) * 1000:.0f} ms; sorted() (C): {(t2 - t1) * 1000:.0f} ms")
# Timsort adapts to existing order
data = [rng.random() for _ in range(200_000)]
for label, xs in [("random", data), ("already sorted", sorted(data)),
("reversed", sorted(data, reverse=True))]:
start = time.perf_counter()
sorted(xs)
print(f"sorted() on {label:>14} data: {(time.perf_counter() - start) * 1000:6.1f} ms")The first race is closer than the asymptotics suggest, and on some machines the built-in sorted wins despite doing asymptotically more work: it is written in C, while counting_sort runs as Python bytecode, with a much larger constant per step. Asymptotics tell you who wins for large enough ; constants decide the races at the sizes you actually have. The second experiment shows Timsort's adaptivity: sorted and reversed inputs are single runs and are handled in linear time.
Common misconceptions
Misconception
Binary search on unsorted data. It runs and returns an answer, but the answer means nothing: the proof used sortedness in its key step. Sort first, or use a set or dictionary for membership.
Misconception
"Quicksort is ." Its worst case is . Its expected time with random pivots is for every input, which is a different and weaker kind of guarantee.
Misconception
"Nothing can sort faster than ." Nothing that sorts by comparing items can. Counting sort and radix sort use the keys themselves and run in linear time when the keys are small integers or short strings.
Misconception
"Python uses quicksort." CPython's sorted and list.sort use Timsort, a stable, adaptive merge sort. NumPy's sort is a different library with its own choices.
Exercises
1. Searching and sorting
Warm-upHumanThe lesson's binary_search runs on a sorted list of 1000 items. What is the largest number of loop iterations it can take?
2. Searching and sorting
CoreHumanIn the lesson's half-open binary search (invariant: everything before lo is , everything from hi on is ), suppose a[mid] >= target. Which update is correct?
3. Searching and sorting
CoreHumanWhich of these sorts are stable, as written or described in the lesson? Choose all that apply.
4. Searching and sorting
CoreHumanUsing the decision-tree argument, what is the smallest number of comparisons that any comparison sort must make, in the worst case, to sort 4 distinct items?
5. Searching and sorting
CoreComputationalThe starter is a common textbook binary search. It finds an occurrence of target, but in a list with repeats such as [1, 2, 2, 2, 3] it may not return the first one. Fix find_first(a, target) so that it returns the index of the first occurrence of target in the sorted list a, or -1 if it is absent, still using reads of a.
The checker counts how many times you read an item: on a million items you may read at most 42.
6. Searching and sorting
CoreComputationalWrite insertion_sort(a) that sorts the list a in place using insertion sort and returns the number of shifts it made (the number of times an item was moved one place to the right). For example, sorting [3, 1, 2] makes 2 shifts.
The tests check the lesson's claim: the number of shifts equals the number of inversions, pairs of positions with .
7. Searching and sorting
CoreComputationalWrite merge_sort(a) that returns a new sorted list (leaving a unchanged), using merge sort. It must be stable: items that compare equal must keep their original order. Compare items only with < or <=.
The checker sorts objects that compare by a number but carry a label, so it can see whether ties kept their order.
8. Searching and sorting
StretchComputationalWrite sort_by_mark(students, max_mark=100). Each student is a tuple (name, mark) with a whole-number mark from 0 to max_mark. Return a new list sorted by mark, lowest first, stably (students with equal marks keep their original order), in time with counting sort, without comparing marks to each other.
The checker's marks refuse to be compared with < or >, so sorted won't help here.
Further reading and resources
- Sorting techniques (Sorting HOW TO) · Python Software FoundationKey functions, stability and multi-key sorting in Python.
- bisect: array bisection algorithm · Python Software Foundation
- listsort.txt: notes on CPython's list sort · Tim Peters and the CPython developersThe design of Timsort in its author's words, including runs, galloping and the merge strategy.
- Extra, extra: read all about it, nearly all binary searches and mergesorts are broken · Joshua Bloch · 2006
- Quicksort · C. A. R. Hoare · 1962
- Nearly-optimal mergesorts: fast, practical sorting methods that optimally adapt to existing runs · J. Ian Munro and Sebastian Wild · 2018The "powersort" merge policy that CPython's list sort now uses.