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

[Terry Reedy]

On 3/8/2015 8:17 PM, nha pham 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

Apply the idea to timsort in python, and try the different cases 
discussed in Tim's documentation.  If it still looks good, open an issue 
with the patch and put tim.peters as nosy.

-- 
Terry Jan Reedy