Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture IX of XIV

Lecture IX · Data Structures & Algorithms

Divide and conquer: mergesort, quicksort, quickselect

Last lecture we sorted honestly and slowly: insertion and selection sort, both O(n2)O(n^2), both fine on a handful of items and hopeless on a million. Today we buy the better price. The whole trick is one idea, and it is almost embarrassingly simple to say out loud: if a problem is hard at size n, cut it into pieces, solve the pieces, and stitch the answers back together.

Split, solve, combine

Here is the move in three words: split the input into smaller versions of the same problem, solve those by the same method, and combine their answers. The recursion bottoms out when a piece is so small the answer is obvious (a list of one element is already sorted). Everything in this lecture is that pattern wearing different clothes.

What makes it fast is worth drawing rather than proving. Suppose splitting and combining a size-n problem costs O(n)O(n), and we split into two halves. Write the total work as a tree. The root does O(n)O(n) work. It hands down two problems of size n/2n/2, and each of those does O(n/2)O(n/2), so the whole second level is O(n)O(n) again. Those four make problems of size n/4n/4, and level three is O(n)O(n) once more. Every level does the same O(n)O(n) total, and the number of levels is however many times you can halve n before you hit 1, which is ⌈log⁡2n⌉\lceil \log_2 n \rceil. So the bill is the work per level times the number of levels: O(n)O(n) times log⁡n\log n, or O(nlog⁡n)O(n \log n).

That is the recurrence

T(n)=2T(n/2)+O(n),T(n) = 2T(n/2) + O(n),

and the tree picture is all the intuition you need for it. Compare it honestly to the quadratic sorts: on a million items, n2n^2 is a trillion, while nlog⁡nn \log n is about twenty million. That gap is not a tweak. It is the difference between a program that finishes and one that does not.

Mergesort, and the merge that does the work

Mergesort is divide and conquer at its most literal. Split the list in half, sort each half by calling yourself, then merge the two sorted halves into one. The splitting is trivial (it is just an index in the middle), and the sorting of the halves is somebody else’s problem, namely a smaller you. All the real work lives in the merge.

So look hard at the merge, because it is the heart of the algorithm and the reason the recurrence has that O(n)O(n) term. You have two runs, each already sorted. Put a finger at the front of each. Whichever finger points at the smaller value, take that value and advance that finger. Repeat until one run runs dry, then pour the rest of the other run on the end (it is already sorted, so nothing more to decide).

def merge(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])   # leftover of a, already in order
    out.extend(b[j:])   # or leftover of b
    return out

Every value is looked at once and copied once, so the merge is O(n)O(n) in the combined length. Three things fall out of this design and you should keep all three. Mergesort is stable: because the test is a[i] <= b[j], equal values keep their original left-to-right order, which matters when you sort records by a second key. Its running time is always O(nlog⁡n)O(n \log n), best case and worst case alike, because the split is blind to the data and never gets unlucky. And it needs extra space: that out list is a whole second array, so mergesort trades memory for its dependable speed. Run it and watch the merge zip two sorted runs together.

python runs in your browser · first run downloads ~240 kb
Plate I Mergesort, run and watched. Press Run: visualize draws the array before and after, then the payoff line merges two sorted runs into one. Edit the input and run again; every value is copied exactly once, which is the O(n)O(n) inside the O(nlog⁡n)O(n \log n).

The sorting race: why nlog⁡nn \log n is another world

Numbers on a page are easy to nod at and hard to feel. The plate below makes the gap visible. It races four sorts on the same shuffled array of twenty-four values: bubble, insertion, and selection, all O(n2)O(n^2), against merge, the lone O(nlog⁡n)O(n \log n). Pick an algorithm and press Play to watch its bars move, the pair being compared lit in ochre and the settled region filling in green. The scoreboard underneath is the real lesson: it counts comparisons and moves for all four algorithms on the current array at once, so you can read the divide-and- conquer discount straight off the table.

Comparison and move counts for four sorting algorithms on a fixed 12-element sample, showing merge sort using far fewer comparisons than the quadratic three.
algorithm order compares moves
Bubble n^2 66 58
Insertion n^2 38 40
Selection n^2 66 22
Merge n log n 32 44

Sample of 12 values; shuffle a live array to watch the race.

Operation counts for every algorithm on the current array.
algorithm order compares moves
Plate II The sorting race. Four sorts on one shuffled array of 24 values; choose one and press Play (compared bars ochre, settled region green), or Step through it. The scoreboard counts comparisons and moves for all four on the current array. Press Shuffle for a fresh array and watch Merge's comparison count stay far below the quadratic three. Speedrun deals a fresh array and scores the attempt on the comparisons you spend, abandoned methods included, against a personal best.

Shuffle a few times and watch what stays true. The three quadratic sorts trade places with each other depending on luck, but merge sits stubbornly far below all of them on comparisons, and the margin only widens as n grows. This is the payoff the tree picture promised, now measured instead of asserted. When somebody says an algorithm is “asymptotically better,” this scoreboard is the thing they mean.

Quicksort: partition in place, then recurse

Mergesort is dependable but greedy with memory. Quicksort is the other famous divide and conquer sort, and it makes the opposite bet: do the rearranging in place, with almost no extra space, and do the hard work before the recursion instead of after.

The hard work is the partition. Pick one element to be the pivot. Walk the rest and shove everything smaller than the pivot to the left, everything larger to the right. Now drop the pivot in the seam between them. The pivot is now in its final sorted position, and you have two smaller unsorted regions on either side. Recurse into both, and there is no combine step at all: once the two sides are sorted, the whole thing is sorted, because the pivot already sits where it belongs.

def quicksort(xs, lo=0, hi=None):
    if hi is None:
        hi = len(xs) - 1
    if lo >= hi:
        return
    p = partition(xs, lo, hi)   # xs[p] is now in its final place
    quicksort(xs, lo, p - 1)    # sort everything left of the pivot
    quicksort(xs, p + 1, hi)    # sort everything right of the pivot

def partition(xs, lo, hi):
    pivot = xs[hi]              # the naive choice: always the last element
    store = lo
    for j in range(lo, hi):
        if xs[j] < pivot:
            xs[store], xs[j] = xs[j], xs[store]
            store += 1
    xs[store], xs[hi] = xs[hi], xs[store]
    return store

When the pivot splits the region into two roughly equal halves, quicksort is the same tree as mergesort and runs in O(nlog⁡n)O(n \log n), and in practice it is often faster than mergesort because it moves data less and touches memory in tidy local sweeps. But notice the word “when.” A good split is not guaranteed. It depends entirely on which element you crown as pivot, and the naive choice above (always the last element) has a dangerous blind spot.

Work that through and the horror shows itself. On the sorted input, the pivot is always the largest element, so partition puts n minus 1 items on the left and zero on the right. The next call faces a problem only one smaller, and the one after that one smaller still. Instead of log⁡n\log n levels of halving you get n levels of shaving one off, each doing O(n)O(n) work, and the total collapses to O(n2)O(n^2). Quicksort’s best case and worst case are genuinely different algorithms in disguise, and the difference is decided by the pivot.

Why randomized pivots are respectable

You could try to outsmart the adversary by hand, and people did for years: take the median of the first, middle, and last elements, say, which defeats the sorted and reversed inputs cheaply. But for any fixed rule for choosing the pivot, a sufficiently determined adversary can construct the input that makes that exact rule choose badly every time. A deterministic pivot has a worst-case input, and if your data comes from someone who wishes you ill, they can hand it to you.

Here is the move that ends the argument, and it is the named idea of this lecture: choose the pivot at random. Not the last element, not the first, a uniformly random element of the current region. Now there is no fixed bad input, because the adversary does not get to see your coin flips. To force the quadratic case they would need the random pivot to land near the extreme almost every single time, and the probability of that is not just small, it is astronomically small, the kind of number with a comma every three digits all the way down. The expected running time becomes O(nlog⁡n)O(n \log n) no matter what input you are handed, and the O(n2)O(n^2) case, while still possible in principle, is something you will never once see in a lifetime of running the program.

This is worth sitting with, because it changes what randomness is for. A random pivot is not sloppiness or a shrug. It is a deliberate engineering tool: you spend one cheap coin flip to buy a guarantee that no input can be your enemy. Randomness here is not the absence of a plan. It is the plan.

Quickselect: the k-th element without sorting

Now the reason partition earns a lecture of its own. Suppose you do not want the whole array sorted. You want a single order statistic: the median, or the tenth smallest, or the ninetieth percentile. Sorting the entire array to read off one position is O(nlog⁡n)O(n \log n) of work to answer a question that, it turns out, only needs O(n)O(n).

Watch what partition gives you for free. After you partition around a pivot, the pivot sits at some index p, which means it is the p-th smallest element, its true rank, decided. Now compare p to the rank k you are hunting. If they match, you are done. If the pivot’s rank is too high, your target is somewhere in the left region, so recurse there and ignore the right entirely. If it is too low, recurse right and forget the left. This is the one difference from quicksort that changes the whole cost: quicksort recurses into both halves, but quickselect recurses into only one, because the answer can live in only one.

That single-sided recursion is why the price drops. With a decent pivot each step throws away a constant fraction of what is left, so the work is n+n/2+n/4+n/8n + n/2 + n/4 + n/8 and on down, a sum that adds up to about 2n2n. Expected O(n)O(n), linear, to find any order statistic without ever sorting the array. And the same random pivot that made quicksort respectable makes quickselect’s linear expectation hold against any input. The plate is a pivot lottery: pick a k, watch a random pivot partition the array and the search collapse into one side while the other goes dark, then re-roll to see the comparison count wander with your luck as the answer stays put.

721259114411315861310

Finding the 5th smallest of 15 values with a fixed middle pivot: the answer is 5, found in 41 comparisons. Load the figure to roll random pivots and watch the search discard one half at a time.

Plate III The pivot lottery. Choose k with the steppers, then Step or Play: the search window stays bright, everything eliminated dims, the random pivot is ochre, and a pivot that reaches its final sorted slot turns green. Re-roll keeps the same array and k but rolls fresh pivots, so the comparison tally changes while the answer never does. Reduced motion jumps straight to the found element.

Re-roll a dozen times on the same k. Some runs get lucky and finish in a handful of comparisons; some are unluckier and take more; none of them ever change the element they find. That is the whole moral of randomization on one screen: luck moves the cost around a little, the correctness never budges, and the expected cost stays linear.

Solving the recurrences honestly

We have now written down three recurrences and waved at all three. That was fine for intuition and it is not good enough to keep, because the three of them are the whole lecture and they differ in ways worth being exact about.

T(n)=2T(n/2)+n,T(n)=T(n−1)+n,T(n)=T(n/2)+n.T(n) = 2T(n/2) + n, \qquad T(n) = T(n-1) + n, \qquad T(n) = T(n/2) + n.

The first is mergesort: two subproblems of half the size, plus linear work to merge. The second is quicksort on its worst day: one subproblem, only one element smaller, plus linear work to partition. The third is quickselect: one subproblem of half the size, plus linear work to partition. They look like three variations on a theme, and they are three different growth classes.

You do not need the Master Theorem to see why, and I would rather you did not reach for it yet, because the counting argument is the thing that will still be with you in ten years. Draw the tree and add up the levels.

For mergesort, every level does nn work in total (one piece of nn, or two of n/2n/2, or four of n/4n/4; the pieces get smaller exactly as fast as they get more numerous) and there are log⁡2n\log_2 n levels because that is how many times you can halve nn. Work per level times number of levels gives nlog⁡nn \log n.

For the shaving recurrence, every level still does about nn work, but the pieces shrink by one instead of halving, so there are nn levels, not log⁡n\log n of them. Now the sum is n+(n−1)+(n−2)+⋯+1n + (n-1) + (n-2) + \cdots + 1, which is n(n+1)/2n(n+1)/2, and quicksort has collapsed to quadratic. Nothing about the partition got worse. The only thing that changed was how fast the subproblem shrinks.

For quickselect, the level count is back to log⁡n\log n because we halve, but each level does only half the work of the one above it, because we throw one side away. The sum is n+n/2+n/4+⋯n + n/2 + n/4 + \cdots, a geometric series that converges to less than 2n2n no matter how many terms you take. That is the whole reason selection is cheaper than sorting: not a smaller number of levels, a shrinking amount of work on each.

python runs in your browser · first run downloads ~240 kb
Plate IV THE THREE SUMS, ADDED UP · The mergesort tree printed level by level (pieces, size, work per level), then all three recurrences totalled side by side as n grows. Press Run and read the columns: the halving sum stays near 2n, the merge column tracks nlog⁡nn\log n, and the shaving column runs away as n2/2n^2/2. At n = 1024 they are 2047, 11264, and 524800.

Three shapes, three answers, and the difference between them is entirely in how much of the problem each step disposes of. Halve and recurse into both sides: nlog⁡nn \log n. Halve and recurse into one: linear. Shave one off and recurse: quadratic. Learn to read a recursive function by asking those two questions, how much smaller and how many of them, and most running times fall out without a theorem.

Quicksort’s worst case, measured

The prose above claimed that a sorted input destroys the last-element pivot, that median-of-three fixes that particular embarrassment, and that a random pivot fixes it in general. Those are all testable claims about comparison counts, so let us stop asserting and start counting: three pivot rules against four inputs, the same partition underneath all of them.

python runs in your browser · first run downloads ~240 kb
Plate V THE PIVOT LEDGER · Quicksort's comparison count on 32 values under three pivot rules and four input shapes. Press Run. The last-element rule pays the full n(n−1)/2n(n-1)/2 on sorted and reversed input; median-of-three fixes exactly those two and nothing else; the random rule is respectable everywhere except the last row, where every value is equal and all three rules fail together.

Read the table one row at a time, because each row makes a different point.

The sorted and reversed rows are the ones we predicted: the last-element pivot pays 496 comparisons on 32 elements, which is exactly n(n−1)/2n(n-1)/2, the full quadratic bill, while median-of-three pays 103 and 126 and the random rule pays 119 and 142. That is a factor of four on thirty-two elements, and the factor is n/log⁡nn/\log n, so it grows without limit. Median-of-three does beautifully here, and that is exactly the trap. It was designed by looking at the inputs that were embarrassing people, and it fixes those. It does not fix the input designed to embarrass it, which exists and can be constructed by anyone who has read your source code. That is the argument for randomization stated as a table rather than as a principle: a deterministic rule has a worst-case input, and its worst case is discoverable by whoever wants to find it.

Now the last row, which is the one people do not expect. Thirty-two identical values, and every rule fails, random included. The reason is not the pivot at all, it is the partition: Lomuto’s sweep asks x[j] < pivot, which is false for every equal element, so nothing moves left, the pivot lands at the very bottom of the region, and the recursion shaves one element off per level. That is the shaving recurrence again, and no amount of coin flipping helps, because every pivot is the same value. Randomization defends you against an unlucky arrangement. It cannot defend you against a degenerate distribution. The fix for that lives in the partition, and it is the three-way split you have already met in the quickselect solution: lows, equals, and highs, with the whole equals block finished in one step.

Partitioning in place: Lomuto and Hoare

Since the partition turned out to be where the bodies are buried, it deserves a proper look. There are two classical schemes, and they differ in more than style.

Lomuto’s is the one printed earlier and the one every textbook shows first, because you can explain it in a sentence: keep a boundary store, sweep j across the region, and whenever you find something smaller than the pivot, swap it down to the boundary and push the boundary right. Its invariant is easy to say out loud, which is its real virtue: everything in xs[lo..store-1] is less than the pivot, everything in xs[store..j-1] is not.

Hoare’s is the original, from the 1961 paper, and it is faster in practice for a reason worth understanding. Instead of one finger sweeping, it starts a finger at each end and walks them toward each other, each stopping when it finds an element belonging on the other side, then swapping the offending pair. Elements only move when they are genuinely on the wrong side, so Hoare does roughly a third of the swaps Lomuto does on random input. The catch is that its pivot is a value, not a slot, so it does not finish with the pivot in its final position; it returns a split point, and the recursion has to include the boundary element rather than skip it. Get that off by one wrong and you recurse forever, which is why the tidier Lomuto is what gets taught.

python runs in your browser · first run downloads ~240 kb
Plate VI TWO PARTITIONS, ONE ARRAY · Lomuto and Hoare run on the same eight values, each reporting where the region split and how many swaps it took, then both run on twelve identical values. Press Run: on the eight values Lomuto needs five swaps to Hoare's two. Then read the last two lines, which are the real point: Lomuto splits the equal array into 0 and 11, the shaving recurrence in the flesh, while Hoare's two fingers meet in the middle and split it 6 and 6.

That last comparison is the practical case for Hoare’s scheme and the reason real implementations use it. On an array of equal values, Lomuto degenerates and Hoare’s fingers stop at every element and cross in the middle, giving a perfect split. The same input, the same pivot policy, two different partitioning disciplines, and one of them is quadratic while the other is nlog⁡nn \log n. Big-O is a property of an algorithm, and the algorithm is not “quicksort”; it is quicksort with this pivot rule and that partition, on this shape of input. The details you are tempted to skim are where the exponent lives.

Merging more than two, and merging lazily

Back to mergesort for a moment, because its merge step generalises in two directions that both show up in real systems.

First, more than two runs. Suppose you have a hundred gigabytes to sort and eight gigabytes of memory. You cannot sort it; you can sort pieces of it. So you read a chunk, sort it, write it out, and repeat until you have a pile of sorted runs on disk. Now you need to merge kk runs at once, and the tournament is the easy way: merge them in pairs, then merge the winners in pairs, and so on. That takes ⌈log⁡2k⌉\lceil \log_2 k \rceil rounds and each round touches every value once, so merging kk runs of nn values in total costs O(nlog⁡k)O(n \log k). This is external mergesort, and it is how databases have sorted things larger than memory since the tape era, for exactly the reason the merge is friendly to slow storage: it reads every run front to back, in order, never jumping around.

Second, and more interesting, the merge does not have to produce a list at all. Look at the merge loop again and notice that it never needs to see the future: at every moment it only compares the two values under its two fingers. So it can hand back one value at a time, on demand, and never allocate the output. In Python that is a generator, and the consequences are not cosmetic. A lazily merged pair of runs costs O(1)O(1) extra space instead of O(n)O(n), and if the caller stops asking after five values, only five values were ever produced.

python runs in your browser · first run downloads ~240 kb
Plate VII MERGING, TWO WAYS · A tournament merge of four sorted runs into one, drawn by visualize, then a lazy merge that yields values on demand. Press Run: the last two lines take the five smallest values out of two hundred without merging the two hundred, because the loop simply stops being asked.

That last trick is worth filing away, because “the k smallest of several sorted sources” is an extremely common request (the first page of results, the ten most recent events across twelve servers) and the naive answer, merge everything then take the front, does an enormous amount of work nobody asked for. Divide and conquer gave us a merge; laziness turns that merge into a stream. The same three lines, asked for less.

Quickselect’s linear expectation, measured

One last accounting. We argued that quickselect is expected O(n)O(n) because the work sums to n+n/2+n/4+⋯n + n/2 + n/4 + \cdots, under 2n2n. That argument has a soft spot, and an honest lecture points at it: the pivot does not actually split the array in half. A random pivot splits it somewhere uniformly random, which is usually worse than half and occasionally much worse.

The argument survives, and here is the repair. Call a pivot good if it falls in the middle half of the region, so that neither side is more than three quarters of what you started with. A uniformly random pivot is good with probability one half, so you expect to flip a coin about twice before getting one, and each good pivot shrinks the problem by at least a factor of 3/43/4. So the expected work is at most 2(n+34n+916n+⋯ )=8n2(n + \tfrac{3}{4}n + \tfrac{9}{16}n + \cdots) = 8n. A worse constant than the tidy 2n2n, still firmly linear, and now honestly derived. This is the standard shape of an expected-time argument: do not hope for the best split, prove that a good-enough split happens often enough.

python runs in your browser · first run downloads ~240 kb
Plate VIII FORTY ROLLS OF THE DICE · Quickselect finds the median of 400 shuffled values forty times over, with fresh random pivots each run. Press Run: the answer is identical in all forty runs while the comparison count wanders from about 750 to about 2350, and the mean lands near 1260, comfortably between the idealised 2n and the 8n the honest argument proves. A full sort of the same array would need about 3456 comparisons to learn the same one number.

Look at the three numbers on the comparison line and then at the one on the line above it. The cost moved; the answer did not. That is the deal randomization offers and it is worth stating plainly one last time, because it is the intellectual content of this lecture more than any particular sort. We did not make the algorithm probably-correct. It is always correct. We made its cost random, and then we proved that the random cost is small in expectation, no matter what input we are handed. Correctness is not up for negotiation. Cost is, and cost is the thing luck is allowed to touch.

Problems

Work these in order. The last one runs its own checks; make every row green.

  1. The recurrence, by hand. Mergesort on 8 elements makes how many levels of merging, and how much total work happens at each level? Write out T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n) for n=8n = 8 and confirm that the levels multiply out to roughly nlog⁡nn \log n. You do not need a formula; the tree picture is the argument.

  2. Stability, felt. You have pairs (name, age) and you sort them by age with mergesort, and two people share an age. Which one ends up first, and why does the <= in the merge (rather than <) decide it? Give a one-sentence reason a stable sort is the one you want when sorting by a second key.

  3. The adversary. For quicksort with the last-element pivot, give a 6-element input that forces the O(n2)O(n^2) behavior, and explain in one sentence how a random pivot would rescue the same input. Then say why no fixed pivot rule can escape having some bad input of its own.

  4. Both sides versus one. In one or two sentences, explain why quicksort is O(nlog⁡n)O(n \log n) expected but quickselect is O(n)O(n) expected, given that both use the exact same partition. The answer is a single word about how many sides each one recurses into; say why that word changes the sum.

  5. The main event. Implement quickselect(a, k) so it returns the k-th smallest element (0-indexed) by partitioning around a pivot and recursing into only the side that can hold rank k. The checks sort the array and demand you agree at every rank, at both ends, with duplicates present, and on a one-element list. Press Run to grade.

    The checks · run against your code

    # quickselect agrees with a full sort at every rank
    a = [8, 3, 11, 1, 6, 10, 2, 7, 4, 9, 5]
    srt = sorted(a)
    assert all(quickselect(a, k) == srt[k] for k in range(len(a)))
    # the ends: k=0 is the minimum, k=n-1 is the maximum
    assert quickselect(a, 0) == min(a)
    assert quickselect(a, len(a) - 1) == max(a)
    # duplicates must not throw the counting off
    b = [4, 1, 4, 1, 4, 2, 2]
    assert quickselect(b, 3) == sorted(b)[3]
    # a one-element list is its own answer
    assert quickselect([42], 0) == 42
    python runs in your browser · first run downloads ~240 kb
    Plate IX Quickselect, graded. Partition around a pivot, then recurse into the one side that can contain rank k; the other side never needs sorting. Run checks your answer against a full sort at every position; Trace lets you step the recursion if a row stays red.
    Hint one

    You do not have to partition in place to get the idea across. Pick a pivot value, then build three lists in one pass: everything less than the pivot, everything equal to it, and everything greater. The lengths of those three lists tell you exactly which one rank k falls into.

    Hint two

    Let lows, equals, and highs be those three lists. If k < len(lows), the answer is the k-th smallest of lows. If k lands inside the equals block, the answer is the pivot itself. Otherwise it is in highs, but you must subtract the elements you skipped: recurse with k - len(lows) - len(equals). Recurse into one list only.

    The solution

    A three-way split makes duplicates painless and the recursion obviously one-sided:

    def quickselect(a, k):
      if len(a) == 1:
          return a[0]
      pivot = a[len(a) // 2]          # any element works; random is what you'd ship
      lows   = [x for x in a if x < pivot]
      equals = [x for x in a if x == pivot]
      highs  = [x for x in a if x > pivot]
      if k < len(lows):
          return quickselect(lows, k)
      elif k < len(lows) + len(equals):
          return pivot
      else:
          return quickselect(highs, k - len(lows) - len(equals))

    Each call recurses into exactly one of the three lists, so the work is n plus a fraction of n plus a fraction of that, summing to expected O(n)O(n). The equals block is what keeps duplicates honest: without it, a value that appears many times could be miscounted and the ranks would drift. Swapping a[len(a) // 2] for random.choice(a) is the one change that turns “usually linear” into “linear against any input an adversary can build,” which is the whole reason we bothered to make the pivot respectable.

  6. Merging more than two. Implement merge_k(runs), which takes a list of already-sorted lists and returns a single sorted list of everything in them. Concatenating and calling sorted is forbidden, and would waste the fact that the runs are sorted already. Merge in pairs, then merge the winners in pairs, until one run is left. This is external mergesort’s inner loop, and the checks include an odd number of runs, empty runs, and no runs at all.

    The checks · run against your code

    # no runs at all
    assert merge_k([]) == []
    # one run comes back as itself
    assert merge_k([[1, 2, 3]]) == [1, 2, 3]
    # two runs interleave
    assert merge_k([[1, 4, 9], [2, 3, 11]]) == [1, 2, 3, 4, 9, 11]
    # an odd number of runs, so one has to ride to the next round
    assert merge_k([[1, 4, 9], [2, 3, 11], [0, 7]]) == [0, 1, 2, 3, 4, 7, 9, 11]
    # empty runs mixed in with full ones
    assert merge_k([[], [2], [], [1, 3]]) == [1, 2, 3]
    # every duplicate survives
    assert merge_k([[2, 2], [2], [1, 2]]) == [1, 2, 2, 2, 2]
    # a bigger instance must agree with a full sort
    rs = [[1, 4, 9], [2, 3, 11], [0, 7], [5, 6, 8, 10]]
    flat = []
    for r in rs:
        flat.extend(r)
    assert merge_k(rs) == sorted(flat)
    python runs in your browser · first run downloads ~240 kb
    Plate X THE TOURNAMENT, GRADED · Merge k sorted runs into one by repeated pairwise merging. Run to grade against seven checks: no runs, one run, an odd count where somebody has to sit out a round, empty runs mixed in, duplicates, and a four-run instance that must agree with a full sort.
    Hint one

    Write the two-run merge first, exactly as in Plate I: two indices, take the smaller of the two fronts, and pour the leftover of whichever run survives onto the end. Everything else is a loop around that function.

    Hint two

    Then loop while len(runs) > 1. Build a new list by merging runs[0] with runs[1], runs[2] with runs[3], and so on. If the count is odd, the last run has no partner this round, so carry it forward unmerged. Replace runs with the new list and go round again. Handle the empty input at the end by returning [] when nothing is left.

    The solution

    The tournament halves the number of runs every round, so it finishes in ⌈log⁡2k⌉\lceil \log_2 k \rceil rounds with every value touched once per round:

    def merge_k(runs):
      def merge_two(a, b):
          out = []
          i = j = 0
          while i < len(a) and j < len(b):
              if a[i] <= b[j]:
                  out.append(a[i]); i += 1
              else:
                  out.append(b[j]); j += 1
          out.extend(a[i:])
          out.extend(b[j:])
          return out
    
      while len(runs) > 1:
          nxt = []
          for i in range(0, len(runs) - 1, 2):
              nxt.append(merge_two(runs[i], runs[i + 1]))
          if len(runs) % 2 == 1:
              nxt.append(runs[-1])
          runs = nxt
      return runs[0] if runs else []

    The total cost is O(nlog⁡k)O(n \log k) for nn values in kk runs. Merging them one at a time into a growing accumulator instead (“merge run 1 into the result, then run 2, then run 3”) is the tempting alternative and it costs O(nk)O(nk), because the accumulator is re-copied on every merge. Same operations, arranged as a tournament rather than a chain, and the exponent moves. That rearrangement is the entire idea of divide and conquer, showing up one last time.

  7. In place, for real. Implement partition(xs, lo, hi): rearrange the region xs[lo..hi] around the pivot value xs[hi], in place, and return the index where the pivot ends up. No new lists, and nothing outside the region may move. This is Lomuto’s scheme, and the checks are written as its postcondition rather than as expected outputs, which is how you should be testing a rearrangement anyway.

    The checks · run against your code

    # the postcondition holds: smaller on the left, not-smaller on the right
    xs = [8, 3, 11, 1, 6, 10, 2, 7]
    p = partition(xs, 0, len(xs) - 1)
    assert all(v < xs[p] for v in xs[:p])
    assert all(v >= xs[p] for v in xs[p + 1:])
    # the pivot lands at its true rank
    assert xs[p] == 7 and p == 4
    # nothing is created or lost: it is still a permutation
    assert sorted(xs) == [1, 2, 3, 6, 7, 8, 10, 11]
    # a two-element region
    ys = [2, 1]
    assert partition(ys, 0, 1) == 0 and ys == [1, 2]
    # an already-sorted region leaves the pivot at the end
    zs = [1, 2, 3, 4]
    assert partition(zs, 0, 3) == 3 and zs == [1, 2, 3, 4]
    # a sub-range only: index 0 must be untouched
    ws = [99, 5, 1, 3, -7]
    assert partition(ws, 1, 4) == 1
    assert ws[0] == 99
    python runs in your browser · first run downloads ~240 kb
    Plate XI LOMUTO, GRADED · The checks state the postcondition directly: everything left of the returned index is smaller than the pivot, everything right of it is not, the array is still a permutation of what it was, and a call on a sub-range leaves the rest of the list alone.
    Hint one

    Save pivot = xs[hi] first, because that slot is going to be overwritten at the end. Then keep a boundary index store, starting at lo, whose meaning never changes: everything from lo up to but not including store is already known to be smaller than the pivot.

    Hint two

    Sweep j from lo to hi - 1. When xs[j] < pivot, swap xs[store] with xs[j] and advance store; otherwise do nothing at all and let j move on. When the sweep ends, one final swap puts the pivot itself at store, which is exactly the seam between the two regions. Return store.

    The solution

    One sweep, one boundary, and a closing swap that drops the pivot into the seam:

    def partition(xs, lo, hi):
      pivot = xs[hi]
      store = lo
      for j in range(lo, hi):
          if xs[j] < pivot:
              xs[store], xs[j] = xs[j], xs[store]
              store += 1
      xs[store], xs[hi] = xs[hi], xs[store]
      return store

    Every element is looked at once, so the partition is O(n)O(n) in the size of the region and uses no extra space beyond two indices. Notice the already-sorted check: the sweep swaps every element with itself, the boundary marches all the way to hi, and the pivot ends up back where it started at the very end of the region. That is the degenerate split from the pivot ledger, produced by hand, and it is worth seeing your own code do it.

  8. The main event, part two. Implement count_inversions(a): the number of pairs of positions i < j with a[i] > a[j], that is, the number of pairs that are in the wrong order. It measures how far from sorted a list is, and it is the standard way to compare two rankings. The naive double loop is O(n2)O(n^2) and is not accepted here; do it in O(nlog⁡n)O(n \log n) by counting inside a merge sort. The caller’s list must come back untouched.

    The checks · run against your code

    # a sorted list has none
    assert count_inversions([1, 2, 3, 4]) == 0
    # a reversed list has every pair: n(n-1)/2
    assert count_inversions([4, 3, 2, 1]) == 6
    # one adjacent swap is exactly one inversion
    assert count_inversions([1, 3, 2, 4]) == 1
    # the textbook instance
    assert count_inversions([2, 4, 1, 3, 5]) == 3
    # equal values are not out of order
    assert count_inversions([2, 2, 2]) == 0
    # the tiny cases
    assert count_inversions([]) == 0
    assert count_inversions([9]) == 0
    # the caller's list must survive
    a = [3, 1, 2]
    assert count_inversions(a) == 2
    assert a == [3, 1, 2]
    # a longer reversed list, where a quadratic scan would still be right but slow
    assert count_inversions(list(range(30, 0, -1))) == 435
    python runs in your browser · first run downloads ~240 kb
    Plate XII INVERSIONS, GRADED · Count the out-of-order pairs in O(nlog⁡n)O(n \log n) by counting during the merge. Run to grade against nine checks: sorted, reversed, one adjacent swap, ties, the empty and single-element lists, an untouched input, and a 30-element reversal whose answer is 435.
    Hint one

    Start from mergesort and have it return two things: the sorted list and a count. The count for a region is the count from the left half, plus the count from the right half, plus however many inversions the merge itself discovers between the two halves. Every pair of positions lands in exactly one of those three buckets, which is why nothing is double-counted.

    Hint two

    Now the one insight. During the merge, when you take a value from the right run because it is strictly smaller than the front of the left run, that value has just jumped ahead of every value still waiting in the left run, and each of those is an inversion. So add len(left) - i to the count at that moment, where i is how far into the left run you have got. Keep the comparison left[i] <= right[j] so that ties are not counted as inversions.

    The solution

    Mergesort with a counter threaded through it. The whole algorithm is the ordinary merge plus one addition:

    def count_inversions(a):
      def go(xs):
          if len(xs) <= 1:
              return xs, 0
          mid = len(xs) // 2
          left, cl = go(xs[:mid])
          right, cr = go(xs[mid:])
          out, i, j, c = [], 0, 0, cl + cr
          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
                  c += len(left) - i      # this value jumped the whole left tail
          out.extend(left[i:])
          out.extend(right[j:])
          return out, c
    
      return go(a[:])[1]

    The slicing at the top, a[:], is what protects the caller’s list, and the recursion works on copies throughout. The cost is the mergesort recurrence unchanged, T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n), because counting added one addition inside a loop that was already running: O(nlog⁡n)O(n \log n) for a quantity that can be as large as n(n−1)/2n(n-1)/2, which is a pleasant thing to be able to say. You have just computed something bigger than the input in less time than it would take to write it down, which is only possible because you never enumerated the pairs, you counted them in blocks.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.