Considering merge optimizations from Timsort in __move_merge_adaptive, __move_merge_adaptive_backward

[jrmarsha <jrmarsha at mtu dot edu>]

Hello all,

This was recently asked in libc-help and I was redirected here.

I've been implementing a new version of Timsort in C++ using more 
standard facilities. One thing I've come across which adds a divide 
between a larger codebase and faster code is the implementation of 
std::inplace_merge with sufficient memory. This goes to the specific 
functions __move_merge_adaptive, and __move_merge_adaptive_backward. In 
particular, there is an optimization where each insertion searches for 
the maximum number of elements it can move. A brief in context 
explanation is here: 
https://en.wikipedia.org/wiki/Timsort#Individual_merges . Would such a 
trick have a place in glibc or is the overhead likely too great in the 
general case?

It was mentioned that there may be ways to tune inplace_merge in such a 
way as to make this happen, but I'm not sure how to approach that.