Re: Sort on vectors slow

[Marius Vollmer]

Marius Vollmer <address@hidden> writes:

> Roland Orre <address@hidden> writes:
>
>> I'm not sure if this huge difference makes sense, or if it indicates
>> a problem with quicksort, which I took from libc earlier (1998).
>
> The problem is not with quicksort per se, but with the insertion sort
> 'optimizations' in our code.  That part takes most of the time, but it
> shouldn't.  I can't say yet what is wrong exactly, yet...

Let me post a short update, in case you are working on this as well,
Roland: it looks like our quicksort isn't sorting correctly all the
time and the subsequent insertion sort covers up for that, but takes
its usual n^2 time for it.

Now, time to get out the Knuth...

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405