[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Misc. Bugs & Problems
"Steve Scheele" <sscheele@scitor.com> writes:
> < Problem: Sort slows down considerably when sorting integer arrays
> > containing many identical values. (on NT)
>
> >Note that this seems to be platform dependent.
>
> Yes - It is also my understanding that Sort uses the sort algorithm
> that is native to the particular OS. I had thought that Sort used
> quick sort. However, quick sort slows down considerably when
> sorting arrays already in (mostly) sorted order. My testing failed
> to show this particular problem.
Only naive quicksort slows down on sorted elements. The usual variant
is the median of three quicksort picking the pivot from a median of
first, last and middle element of a range. The most inefficient
configuration for this sort is pretty hard to come up by design, but
is also O(n^2).
When you are using the GNU C library, qsort really reverts to a
mergesort method unless memory is scarce.
--
David Kastrup Phone: +49-234-700-5570
Email: dak@neuroinformatik.ruhr-uni-bochum.de Fax: +49-234-709-4209
Institut für Neuroinformatik, Universitätsstr. 150, 44780 Bochum, Germany