Improvement to std::sort<>, was: Improvement to std::copy<>

[Matt Austern]

On Thursday, August 14, 2003, at 09:29  AM, Dhruv Matani wrote:

> Oops, sorry that's std::sort<>. I guess some sleep is on the menu!!!
>
> -Dhruv.
>
> On Thu, 2003-08-14 at 21:48, Dhruv Matani wrote:
>> I went through the std::copy algorithm, and it seems that it uses the
>> insertion sort algorithm. I have tried to modify the unguarded 
>> insertion
>> function to be faster. The results show very minor improvements, but I
>> guess that can be improved. Now, instead of iterating through the 
>> entire
>> array form the last element, it uses binary sort to find the corerect
>> postion for insertion, and then uses std::copy backward to actually 
>> move
>> the elements, because copy backwward might be optimized for some data
>> types. I can post the code if needed.

You mean 'binary search', right?

It's not obvious to me that this will be an improvement in general.  We
don't fall back to insertion sort until the final steps, when the array
is almost sorted.  (In principle we could just use quicksort all the
way down, but switching to insertion sort is faster.)  Traipsing through
the entire array does mean that we examine some elements unnecessary,
but a simple linear access pattern is good for locality.

			--Matt