Divide and Conquer: Merge Sort and Quicksort

1Split, solve, combine

Three steps that show up everywhere from sorting to matrix multiplication to fast Fourier transforms.

Divide and conquer is three steps:

1. Divide the problem into smaller instances of the same problem.
2. Conquer each one recursively (base case: it is small enough to solve outright).
3. Combine the sub-answers into the answer.

The cost of the whole thing depends on where the work lives:

2Merge sort

The reliable one. O(n log n) on every input without exception, stable, and it pays for that with memory.

Splitting is trivial — take the midpoint. All the work is in the merge, and the merge is the routine you already wrote in Chapter 5: walk two sorted sequences, repeatedly taking whichever front value is smaller.

def merge_sort(xs):
    if len(xs) <= 1:            # base case: already sorted
        return xs

    mid = len(xs) // 2          # 1. DIVIDE
    left = merge_sort(xs[:mid])   # 2. CONQUER
    right = merge_sort(xs[mid:])
    return merge(left, right)     # 3. COMBINE


def merge(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:        # <= not <, and that is what keeps it STABLE
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])           # one side is exhausted; the other is
    out.extend(b[j:])           # already sorted, so append it wholesale
    return out

The uniformity is the selling point. Merge sort does not care about the input: sorted, reversed, random, adversarial — always n log n. That makes it the right choice when you need a guarantee rather than an average.

The price is O(n) extra memory for the merge buffers. In-place merge sort exists but is complicated and slower in practice, so almost nobody uses it.

3Quicksort

The fast one. Same asymptotics on average, better constants, sorts in place — and it has a genuine failure mode.

Quicksort moves the work to the other end. Instead of splitting blindly and merging carefully, it partitions carefully and then has nothing to combine at all.

Pick a pivot. Rearrange the array so everything smaller is left of it and everything larger is right of it. The pivot is now in its final position — permanently — and the two sides are independent subproblems.

def quicksort(xs, lo=0, hi=None):
    if hi is None:
        hi = len(xs) - 1
    if lo >= hi:
        return xs
    p = partition(xs, lo, hi)
    quicksort(xs, lo, p - 1)      # everything left of the pivot
    quicksort(xs, p + 1, hi)      # everything right of it
    return xs                     # no combine step — it is already sorted


def partition(xs, lo, hi):
    """Lomuto partition. Returns the pivot's final index."""
    pivot = xs[hi]
    i = lo                        # boundary of the B region
    for j in range(lo, hi):
        if xs[j] < pivot:
            xs[i], xs[j] = xs[j], xs[i]
            i += 1
    xs[i], xs[hi] = xs[hi], xs[i] # put the pivot between the two regions
    return i

Why it beats merge sort in practice

• No allocation. Partitioning happens in the array itself.
• Cache locality. Partitioning is a linear scan over contiguous memory, which is what CPUs are fastest at.
• Small constant. A swap is cheaper than an append plus a copy.

The three standard defences

import random

# 1. Random pivot — an adversary cannot predict it
def partition_random(xs, lo, hi):
    r = random.randint(lo, hi)
    xs[r], xs[hi] = xs[hi], xs[r]
    return partition(xs, lo, hi)

# 2. Median of three — cheap, and immune to sorted input specifically
def median_of_three(xs, lo, hi):
    mid = (lo + hi) // 2
    trio = sorted([(xs[lo], lo), (xs[mid], mid), (xs[hi], hi)])
    return trio[1][1]                # index of the median value

# 3. Introsort — track the recursion depth, and if it exceeds
#    2*log(n), abandon quicksort and finish with heapsort.
#    This is what C++As speed with
#    merge sort's guarantee.

4Merge sort versus quicksort

Both O(n log n) on average. They differ in every other respect, and the differences decide real choices.

Notice the Java row. Arrays.sort uses quicksort for int[] and merge sort for Object[]. That is not inconsistency — it is the stability requirement. Primitives are indistinguishable when equal, so stability is meaningless and speed wins. Objects can be equal by key but distinct, so stability matters and merge sort wins.

What real libraries actually ship

• Timsort (Python, Java objects, Rust, Android): merge sort that finds existing sorted runs and merges them, with insertion sort for short runs. O(n) on already-sorted data, which is common. Stable.
• Introsort (C++ std::sort): quicksort, switching to heapsort if the recursion gets too deep, and to insertion sort for small ranges. Not stable, but O(n log n) guaranteed.
• Pattern-defeating quicksort (Rust unstable sort, modern C++): detects adversarial patterns and adapts.

5The n log n barrier

No comparison sort can do better than O(n log n). Here is the proof, and here is how to cheat.

The argument is short and worth understanding, because it is a rare case where we can say something is impossible rather than merely difficult.

1. A list of n distinct items has n! possible orderings. Exactly one is sorted.
2. Each comparison has two outcomes, so it can at best halve the set of orderings still consistent with what you know.
3. To get from n! possibilities down to 1 by halving, you need at least log₂(n!) comparisons.
4. By Stirling's approximation, log₂(n!) is about n log₂ n.

So O(n log n) is not a limit of our cleverness. It is a limit of comparison as a way of learning about data.

Counting sort

If the values are integers in a known small range, do not compare them at all. Count them.

def counting_sort(xs, max_value):
    counts = [0] * (max_value + 1)
    for x in xs:
        counts[x] += 1              # tally — no comparison anywhere

    out = []
    for value, n in enumerate(counts):
        out.extend([value] * n)     # read the tallies back in order
    return out

# O(n + k) where k is the value range. When k is small this is LINEAR,
# which is impossible for a comparison sort.
#
# When k is large it is a disaster: sorting [1, 1000000000] allocates
# a billion counters. The trade is explicit and unforgiving.

>_Playground

Race the sorts, then feed quicksort its worst case and watch it fall over.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.