]> git.ipfire.org Git - thirdparty/Python/cpython.git/commit
gh-135551: Change how sorting picks minimum run length (#135553)
authorTim Peters <tim.peters@gmail.com>
Fri, 27 Jun 2025 04:48:05 +0000 (23:48 -0500)
committerGitHub <noreply@github.com>
Fri, 27 Jun 2025 04:48:05 +0000 (23:48 -0500)
commit2fc68e180ffdb31886938203e89a75b220a58cec
tree277ac5b1fbbecd63f077756bf2e7f62fa65d3a41
parentb38810bab76c11ea09260a817b3354aebc2af580
gh-135551: Change how sorting picks minimum run length (#135553)

New scheme from Stefan Pochmann for picking minimum run lengths.

By allowing them to change a little from one run to the next, it's possible to
arrange for that all merges, at all levels, strongly tend to be as evenly balanced
as possible, for randomly ordered data. Meaning the number of initial runs is a
power of 2, and all merges involve runs whose lengths differ by no more than 1.
Misc/ACKS
Misc/NEWS.d/next/Core_and_Builtins/2025-06-16-03-56-15.gh-issue-135551.hRTQO-.rst [new file with mode: 0644]
Objects/listobject.c
Objects/listsort.txt