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

[Ryan Smith-Roberts]

I suspect that you will find the Python community extremely conservative
about any changes to its sorting algorithm, given that it took thirteen
years and some really impressive automated verification software to find
this bug:

http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/

On Sun, Mar 8, 2015 at 5:17 PM, nha pham <phqnha at gmail.com> wrote:

> We can optimize the TimSort algorithm by optimizing its binary insertion
> sort.
>
>
>
> The current version of binary insertion sort use this idea:
>
> Use binary search to find a final position in sorted list for a new
> element X. Then insert X to that location.
>
>
>
> I suggest another idea:
>
> Use binary search to find a final postion in sorted list for a new element
> X. Before insert X to that location, compare X with its next element.
>
> For the next element, we already know if it is lower or bigger than X, so
> we can reduce the search area to the left side or on the right side of X in
> the sorted list.
>
>
>
> I have applied my idea on java.util. ComparableTimSort.sort() and testing.
> The execute time is reduced by 2%-6% with array of random integer.
>
>
>
> Here is detail about algorithm and testing:
> https://github.com/nhapq/Optimize_binary_insertion_sort
>
>
>
> Sincerely.
>
> phqnha
>
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> https://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe:
> https://mail.python.org/mailman/options/python-dev/rmsr%40lab.net
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20150308/335c9e79/attachment.html>