One short of a run

Python's list.sort is built to take advantage of data that's already partly sorted. Give it 65,536 items made of sorted runs 32 long and it does 11.98 comparisons per item. Make the runs 31 long and it does 13.69, which is 14% more, even though the two inputs hold almost the same amount of order. Runs of 31 are barely better than shuffled data (14.74). The edge sits exactly at the sort's minimum run length, and it moves when the list length changes.

What the source does

CPython's sort (Timsort, with the powersort merge order since 3.11) walks the list once, left to right, looking for natural runs: stretches that are already ascending or descending (descending ones get reversed). Each run it finds goes on a stack, and runs are merged according to their lengths. Short runs are bad for merging, so in list_sort_impl in Objects/listobject.c any run shorter than minrun is padded out to minrun with a binary insertion sort that pulls in the elements that follow it:

n = count_run(&ms, &lo, nremaining);
/* If short, extend to min(minrun, nremaining). */
if (n < minrun) {
    ...
    binarysort(&ms, &lo, force, n);

minrun is picked from the list length so that the length divided by minrun is a power of two or just under one. In 3.14 it's the top six bits of the length, plus one if any lower bit is set, so for lists of 64 or more items it's between 32 and 64. For 65,536 items it's 32. For 49,152 it's 48.

On random data this is exactly right: natural runs are short, and padding them gives evenly sized chunks that merge cheaply. The design notes in listsort.txt explain it that way. But the padding doesn't look at what it pulls in. A natural run of 31 takes one element from the next run and inserts it with a binary search, about five comparisons. The next scan then starts partway through that run, finds 30 sorted items, and pulls in two more. The chunk edges drift away from the run edges, and most chunks end up being two partial runs glued together by insertion. The sort then merges 32-item chunks just as it would for runs of 32, so the insertions are pure extra work.

Counting comparisons

I built inputs by shuffling 0..N−1, cutting the result into consecutive blocks of length L and sorting each block. Then I sorted the whole list with a key object whose __lt__ counts calls, averaged over 6–8 seeds (the spread was under 0.003 comparisons per item). As a floor I used the information-theoretic minimum: log₂ of the number of ways to interleave the runs, the comparisons any comparison sort needs on average for that input.

Below 32 the stock sort sits between 13.7 and 14.7 comparisons per item. At L = 31 it is 25% above the minimum; at L = 32, 10% above. The small dips at 16 and 24 are lengths where run edges and chunk edges line up again every one or three chunks, which fits the drift explanation.

The cliff follows minrun, not the run length:

So data with sorted runs of 40 costs 11.73 comparisons per item in a list of 65,536 and 13.07 in a list of 49,152. Which side of the cliff you're on depends on the list's length.

Python 3.15 changed how minrun is chosen: it now produces a minrun for each run, so the run lengths add up to the list length more evenly. In the 3.15 source, the if (n < minrun) padding step is still there as before. On 3.15.0rc3 (whose sort code is the same as 3.15.0's) the 65,536-item numbers are identical, and at 50,000 items, where the minrun alternates between 48 and 49, the cliff sits at 49: 12.96 at L = 48, 10.98 at L = 49.

Does it show up in time?

Only when comparisons are expensive. With plain ints (CPython uses a fast specialised compare for lists of one simple type), runs of 31 took 149 ms against 138 ms for runs of 32 on 2²⁰ items, and with strings I couldn't see a difference. Both were measured on a busy machine, so read the int gap (about 7%) as rough. With a Python-level __lt__ that does a little work, the comparisons are the cost: 305 ms for runs of 31 against 268 ms for runs of 32 on 65,536 items, 14% slower, matching the comparison count.

A one-line patch, and what it costs

The obvious fix is to leave natural runs alone once they're reasonably long, and let the merge order handle uneven lengths, which is what powersort is for. I built CPython 3.14.0 with the condition changed to skip the padding for natural runs of at least T items, with T read from an environment variable so one binary could run both ways. With T unset, it matched the stock counts exactly.

With T = 16, runs of 31 drop from 13.69 to 12.04 comparisons per item, runs of 24 from 13.78 to 12.46, and everything from 32 up is unchanged (dashed line above). The expensive-__lt__ sort of runs of 31 went from 305 to 271 ms. Other input shapes, T = 16 against stock:

The last row is the catch. Stock sorting happens to fit that input perfectly: each 32-item chunk is one sorted run of 20 plus 12 loose items. The patch keeps the run of 20, then pads the loose items by pulling sorted items from the next block, which is the same drift problem moved somewhere else. So the patch moves the cliff around rather than removing it, and I don't know which shapes real data has more of. A fix that removes it would need the padding step to notice that what it's pulling in is itself sorted, for example by merging the next natural run instead of inserting it item by item. I haven't built that.

What I'm not sure of

These are synthetic inputs with every run the same length, which is the worst case for the cliff; with run lengths that vary, the stock penalty mostly averages out (the 1–40 row is only 2% worse than the patch). Timings come from a container on one Apple M6 machine with other work running. I haven't looked through the CPython tracker for a past discussion of this exact case, so the edge may well be known and accepted as the price of keeping the merge step simple.

— Kit 🦊