Lecture IX · Data Structures & Algorithms
Divide and conquer: mergesort, quicksort, quickselect
Last lecture we sorted honestly and slowly: insertion and selection sort, both , 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 , and we split into two halves. Write the total work as a tree. The root does work. It hands down two problems of size , and each of those does , so the whole second level is again. Those four make problems of size , and level three is once more. Every level does the same total, and the number of levels is however many times you can halve n before you hit 1, which is . So the bill is the work per level times the number of levels: times , or .
That is the recurrence
and the tree picture is all the intuition you need for it. Compare it honestly to the quadratic sorts: on a million items, is a trillion, while 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 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 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 , 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.
The sorting race: why 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 , against merge, the lone . 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.
| 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.
| algorithm | order | compares | moves |
|---|
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 , 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 levels of halving you get n levels of shaving one off, each doing work, and the total collapses to . 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 no matter what input you are handed, and the 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 of work to answer a question that, it turns out, only needs .
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 and on down, a sum that adds up to about . Expected , 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.
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.
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.
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 work in total (one piece of , or two of , or four of ; the pieces get smaller exactly as fast as they get more numerous) and there are levels because that is how many times you can halve . Work per level times number of levels gives .
For the shaving recurrence, every level still does about work, but the pieces shrink by one instead of halving, so there are levels, not of them. Now the sum is , which is , 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 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 , a geometric series that converges to less than 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.
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: . 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.
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 , 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 , 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.
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 . 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 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 rounds and each round touches every value once, so merging runs of values in total costs . 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 extra space instead of , and if the caller stops asking after five values, only five values were ever produced.
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 because the work sums to , under . 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 . So the expected work is at most . A worse constant than the tidy , 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.
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.
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 for and confirm that the levels multiply out to roughly . You do not need a formula; the tree picture is the argument.
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.The adversary. For quicksort with the last-element pivot, give a 6-element input that forces the 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.
Both sides versus one. In one or two sentences, explain why quicksort is expected but quickselect is 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.
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 kbPlate 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, andhighsbe those three lists. Ifk < len(lows), the answer is the k-th smallest oflows. If k lands inside the equals block, the answer is the pivot itself. Otherwise it is inhighs, but you must subtract the elements you skipped: recurse withk - 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 . The
equalsblock is what keeps duplicates honest: without it, a value that appears many times could be miscounted and the ranks would drift. Swappinga[len(a) // 2]forrandom.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.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 callingsortedis 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 kbPlate 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 mergingruns[0]withruns[1],runs[2]withruns[3], and so on. If the count is odd, the last run has no partner this round, so carry it forward unmerged. Replacerunswith 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 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 for values in 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 , 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.
In place, for real. Implement
partition(xs, lo, hi): rearrange the regionxs[lo..hi]around the pivot valuexs[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 kbPlate 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 indexstore, starting atlo, whose meaning never changes: everything fromloup to but not includingstoreis already known to be smaller than the pivot.Hint two
Sweep
jfromlotohi - 1. Whenxs[j] < pivot, swapxs[store]withxs[j]and advancestore; otherwise do nothing at all and letjmove on. When the sweep ends, one final swap puts the pivot itself atstore, which is exactly the seam between the two regions. Returnstore.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 storeEvery element is looked at once, so the partition is 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.The main event, part two. Implement
count_inversions(a): the number of pairs of positionsi < jwitha[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 and is not accepted here; do it in 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 kbPlate XII INVERSIONS, GRADED · Count the out-of-order pairs in 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) - ito the count at that moment, whereiis how far into the left run you have got. Keep the comparisonleft[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, , because counting added one addition inside a loop that was already running: for a quantity that can be as large as , 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.