Re: Sort on vectors slow

[Marius Vollmer]

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

> I've found in some text though that time complexity of quicksort is
> O(N^2) in worst case, only O(N log N) in average, and merge sort is
> O(N log N) in all cases.

The worst case being an already sorted vector, right?  This shouldn't
be the case with your random vector.

In any case, the qsort function in GNU libc is now implemented as a
merge sort.  From libc NEWS:

* Mike Haertel (of GNU e?grep and malloc fame) has written a new sorting
  function which uses the `merge sort' algorithm, and is said to be
  significantly faster than the old GNU `qsort' function.  Merge sort is
  now the standard `qsort' function.  The new algorithm can require a lot
  of temporary storage; so, the old sorting function is called when the
  required storage is not available.

> PS. Code to the restricted-vector-msort! below. I suggest that this
> should go into the distribution, alternatively we should replace the
> current default quicksort for vectors with merge sort.

Yep, I will probably do this, but according to the NEWS entry above,
we might need to fall back to quicksort; so fixing quicksort would be
good in any case.