This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Improvement to std::sort<>, was: Improvement to std::copy<>
- From: Matt Austern <austern at apple dot com>
- To: Dhruv Matani <dhruvbird at gmx dot net>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Thu, 14 Aug 2003 11:03:48 -0700
- Subject: Re: Improvement to std::sort<>, was: Improvement to std::copy<>
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