[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