Sorting (was RE: A better self)

[Terry Reedy]

"Tim Peters" <tim.one at comcast.net> wrote in message
news:mailman.1028434088.30751.python-list at python.org...
> [Timsort] is checked in now (yay!), and will be "the sort" in Python
2.3.
> Extensive information about it can be found in the patch report and
its
> attachments:
>
>      http://www.python.org/sf/587076

The attachments include timsort.txt.  Here is a quick summary:

1. View the sequence of N items to be sorted as, and convert it to, a
sequence of K ascending runs (down runs are reversed).  To avoid the
overhead of merging small runs, use binary insertsort to bring run
lengths up to a minimum (depending on N) in the range [32,64].
Consequence: a list sorted in ascending order or descending order
without duplicates will be detected as one run and left as is or
simply reversed.

2. For K >= 2, timsort(runs) = timmerge(timsort(runs[:j]),
timesort(runs[j:])).  Note: the merge tree is constructed from the
bottom up rather than from the top down as might be implied by the
above description.

3. Merge intelligently (including 'galloping') to minimize compares
and moves and exploit nonrandom structure in the original list.

Terry J. Reedy