[Python-Dev] Tunning binary insertion sort algorithm in Timsort.

[Armin Rigo]

Hi Tim,

On 10 March 2015 at 18:22, Tim Peters <tim.peters at gmail.com> wrote:
> 1. Merge "2 at a time" instead of just 1.  That is, first "sort" the
> next 2 elements to be merged (1 compare and a possible swap).  Then
> binary search to find where the smaller belongs, and a shorter binary
> search to find where the larger belongs.  Then shift both into place.

Good idea, but when I tried that it seemed to increase the total
number of comparisons (on random inputs with only up to 136 items).
The increase is on the order of 5%.  I'm not sure reduced data
movement can compensate for that in Python.

Test and code available here:
https://bitbucket.org/arigo/arigo/src/default/hack/pypy-hack/list_sort/

The change to insert two items at a time is here:
https://bitbucket.org/arigo/arigo/commits/68e04d143dc242cfd9e3934451321f685a68a8e2

(This is taken straight from PyPy's code.)


A bientôt,

Armin.