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

[Raja R Harinath <harinath at cs dot umn dot edu>]

Hi,

Matt Austern <austern@apple.com> writes:

> 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.

Also, at the end of the quicksort pass, each element of the array
will be within 'n' elements of it's rightful place, where 'n' is the
threshold below which the quicksort will not recurse.  So, binary
searches on the whole array will be counterproductive.  A binary
search within a '2n' neighbourhood may be feasible, but probably not
worth it, since for those values of 'n', log 2n will be close to n/2.

- Hari
-- 
Raja R Harinath ------------------------------ harinath@cs.umn.edu