Skip to content
LumenaryAcademy
Core 85 min

Searching and sorting

Binary search and why it is correct, the classic sorting algorithms, the n log n barrier, and how Python really sorts.

Code tested · 8AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

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.

Worked examplesH

Linear and binary search

Linear search checks the items one by one. It works on any list, sorted or not, and costs Θ(n)\Theta(n) 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.

python
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 lo

It 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 ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 iterations (for n=len(a)≥1n = \texttt{len(a)} \ge 1) and returns the smallest index ii with ai≥ta_i \ge t, or nn if there is none.

Proof

Invariant: every item before position lo is less than tt, and every item at position hi or later is at least tt; and 0≤lo≤hi≤n0 \le \texttt{lo} \le \texttt{hi} \le n.

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 amid<ta_{mid} < t, then because the list is sorted, every aia_i with i≤midi \le mid satisfies ai≤amid<ta_i \le a_{mid} < t, so setting lo = mid + 1 keeps the first part true. Otherwise amid≥ta_{mid} \ge t, and every aia_i with i≥midi \ge mid satisfies ai≥amid≥ta_i \ge a_{mid} \ge t, 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 ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 iterations.

Result. The loop stops when lo == hi. By the invariant, everything before lo is less than tt and everything from lo on is at least tt, so lo is the smallest index with alo≥ta_{lo} \ge t, or nn 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.

python
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)}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

(The pairs show the index found, or −1, and the number of steps.)

Worked examplesH

Two simple sorts

Selection sort repeatedly selects the smallest remaining item and swaps it into place. Its invariant: after ii passes, positions 00 to i−1i-1 hold the ii smallest items, in order.

python
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 n(n−1)/2n(n-1)/2 comparisons, whatever the input, so it is Θ(n2)\Theta(n^2) in every case; its one virtue is that it makes at most n−1n - 1 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 ii, the first i+1i + 1 items are the original first i+1i + 1 items, in sorted order.

python
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] = x

Its cost depends heavily on the input. On a sorted list, the inner loop never runs: n−1n - 1 comparisons, Θ(n)\Theta(n). On a reversed list, item ii shifts past all ii before it: n(n−1)/2n(n-1)/2 shifts, Θ(n2)\Theta(n^2). 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.

Worked examplesH

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 nn items takes at most n−1n - 1 comparisons.

python
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 T(n)=2T(n/2)+Θ(n)T(n) = 2T(n/2) + \Theta(n), which the master theorem of the last lesson solves as Θ(nlog⁡n)\Theta(n \log n), in every case. The price is memory: the merges build new lists, using Θ(n)\Theta(n) extra space.

Worked examplesH

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.

python
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 Θ(n)\Theta(n). If the pivot splits the list roughly in half each time, T(n)=2T(n/2)+Θ(n)=Θ(nlog⁡n)T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n). But if the pivot is always the smallest or largest item, one part is empty and the other has n−1n - 1 items: T(n)=T(n−1)+Θ(n)=Θ(n2)T(n) = T(n-1) + \Theta(n) = \Theta(n^2). 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 2nln⁡n≈1.39 nlog⁡2n2n \ln n \approx 1.39\, n \log_2 n; 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 O(log⁡n)O(\log n) 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 O(nlog⁡n)O(n \log n); 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.

python
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}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

The n log n barrier

Merge sort makes about nlog⁡2nn \log_2 n 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.

yesnoyesnoyesnoyesnoyesnoa ≤ b ?b ≤ c ?a ≤ c ?a b ca ≤ c ?b a cb ≤ c ?a c bc a bb c ac b a
A decision tree for sorting three items a, b, c. Each internal node is a comparison; each leaf is one of the 3! = 6 possible orders. This tree has height 3, and no tree with only 2 levels of comparisons could have 6 leaves.

Theorem— the comparison-sorting lower bound

Every algorithm that sorts nn distinct items using only comparisons between them makes at least ⌈log⁡2(n!)⌉\lceil \log_2 (n!) \rceil comparisons on some input, and log⁡2(n!)=Θ(nlog⁡n)\log_2 (n!) = \Theta(n \log n).

Proof

(Sketch.) Fix nn and an algorithm. Its behaviour on inputs of size nn 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 n!n! leaves. A binary tree of height hh has at most 2h2^h leaves, so 2h≥n!2^h \ge n!, that is h≥log⁡2(n!)h \ge \log_2(n!). The height is the worst-case number of comparisons. Finally, the largest n/2n/2 factors of n!n! are each at least n/2n/2, so n!≥(n/2)n/2n! \ge (n/2)^{n/2} and log⁡2(n!)≥n2log⁡2n2=Ω(nlog⁡n)\log_2(n!) \ge \frac{n}{2}\log_2 \frac{n}{2} = \Omega(n \log n); and n!≤nnn! \le n^n gives the matching upper bound.

∎

So merge sort is asymptotically optimal among comparison sorts, and no amount of cleverness will beat nlog⁡nn \log n by more than a constant factor. (A similar argument shows the average number of comparisons is also Ω(nlog⁡n)\Omega(n \log n).) The bound has a loophole, though: it says nothing about algorithms that do more than compare. We'll use that loophole below.

Worked examplesH

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.

python
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 order
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Timsort

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 Θ(nlog⁡n)\Theta(n \log n) in the worst case and Θ(n)\Theta(n) 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.

ComputationC

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 Θ(n+k)\Theta(n + k) time for nn items with keys in a range of size kk: linear when kk 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.

python
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")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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 nn; 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 misconceptionsH

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 O(nlog⁡n)O(n \log n)." Its worst case is Θ(n2)\Theta(n^2). Its expected time with random pivots is Θ(nlog⁡n)\Theta(n \log n) for every input, which is a different and weaker kind of guarantee.

Misconception

"Nothing can sort faster than nlog⁡nn \log n." 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

Exercises

1. Searching and sorting

Warm-upHuman

The 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

CoreHuman

In the lesson's half-open binary search (invariant: everything before lo is <t< t, everything from hi on is ≥t\ge t), suppose a[mid] >= target. Which update is correct?

Choose one

3. Searching and sorting

CoreHuman

Which of these sorts are stable, as written or described in the lesson? Choose all that apply.

Choose all that apply

4. Searching and sorting

CoreHuman

Using 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

CoreComputational

The 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 O(log⁡n)O(\log n) reads of a.

The checker counts how many times you read an item: on a million items you may read at most 42.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Searching and sorting

CoreComputational

Write 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 i<ji < j with ai>aja_i > a_j.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Searching and sorting

CoreComputational

Write 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.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

8. Searching and sorting

StretchComputational

Write 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 Θ(n+k)\Theta(n + k) 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.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources