Hi Tim, On 10 March 2015 at 18:22, Tim Peters <tim.pet...@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. _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
