Bug report

Bug description:

On randomly ordered data, Python's sort ends up artificially forcing all initial runs to length minrun, whose value is a function of len(list), picked in a cheap way to avoid the very worst cases of imbalance in the final merge.

Stefan Pochmann has invented a much better way, which may vary minrun a little from one run to the next. Under his scheme, at all levels of the merge tree:

The number of runs is a power of 2.
At most two different values of run lengths are in play.
The lengths of run pairs to be merged differ by no more than 1.

So, in all cases, in all ways it's as close to perfectly balanced as possible.

For randomly ordered inputs, this eliminates all cases of "bad imbalance", cuts the average number of compares a little, and cuts the amount of pointer copying due to unbalanced merges.

Following is a Python prototype verifying the claims. Variables starting with "mr_" will become part of the MergeState struct, and the loop body in the generator will become a brief inlined function.

from itertools import accumulate
try:
    from itertools import batched
except ImportError:
    from itertools import islice
    def batched(xs, k):
        it = iter(xs)
        while chunk := tuple(islice(it, k)):
            yield chunk
MAX_MINRUN = 64
def gen_minruns(n):
    # mr_int = minrun's integral part
    # mr_frac = minrun's fractional part with mr_e bits and
    # mask mr_mask
    mr_int = n
    mr_e = 0
    while mr_int >= MAX_MINRUN:
        mr_int >>= 1
        mr_e += 1
    mr_mask = (1 << mr_e) - 1
    mr_frac = n & mr_mask
    mr_current_frac = 0
    while True:
        mr_current_frac += mr_frac
        assert mr_current_frac >> mr_e <= 1
        yield mr_int + (mr_current_frac >> mr_e)
        mr_current_frac &= mr_mask
def chew(n, show=False):
    if n < 1:
        return
    sizes = []
    tot = 0
    for size in gen_minruns(n):
        sizes.append(size)
        tot += size
        if tot >= n:
            break
    assert tot == n
    print(n, len(sizes))
    small, large = 32, 64
    while len(sizes) > 1:
        assert not len(sizes) & 1
        assert len(sizes).bit_count() == 1 # i.e., power of 2
        assert sum(sizes) == n
        assert min(sizes) >= min(n, small)
        assert max(sizes) <= large
        d = set(sizes)
        assert len(d) <= 2
        if len(d) == 2:
            lo, hi = sorted(d)
            assert lo + 1 == hi
        mr = n / len(sizes)
        for i, s in enumerate(accumulate(sizes, initial=0)):
            assert int(mr * i) == s
        newsizes = []
        for a, b in batched(sizes, 2):
            assert abs(a - b) <= 1
            newsizes.append(a + b)
        sizes = newsizes
        smsll = large
        large *= 2
    assert sizes[0] == n
for n in range(2_000_001):
    chew(n)

CPython versions tested on:

3.14, CPython main branch

Operating systems tested on:

Windows

Linked PRs

gh-135551: Change how sorting picks minimum run length #135553