Re: [HACKERS] \dt and disk access

>
> At 9:48 PM 6/23/97, David Friend wrote:
> >On Sun, 22 Jun 1997, Thomas G. Lockhart wrote:
> >
> >> I don't know which Knuth algorithm the code uses, but some sort
> >> algorithms perform very poorly on data which happens to be already
> >> sorted. QuickSort, which comes on many Unix boxes (the qsort() call) is
> >> quickest on completely unordered/disordered data and its slowest
> >> performance is on already perfectly sorted data (I'm doing this from
> >> memory, but the facts may be mostly correct :).
> >
> >From what I remember, the quick sort algorithm works just as fast on
> >sorted data as on unsorted data.  In other words, the algorithm does not
> >take advantage of the fact that the data is sorted.
>
> What Thomas says is correct for the standard textbook description of
> quicksort.  It is not hard to reverse the order of the compare and fix it
> so its worst case is reverse-sorted instead of presorted data.  I would
> expect that most vendor's implementations have this fix, but no guarantees.
>
> I have skipped the first part of this discussion.  Quicksort is a good
> in-memory algorithm for uniprocessors.  It may not be applicable to
> database sorts of very large data sets.

The quicksort is to be used only for in-memory sorting.  Larger sorts
are going to use the Knuth, volume 3, page 280 tape sorting algorithm.

If anyone wants a digest of this discussion, I can easily sent it to
them.

- --
Bruce Momjian
maillist@candle.pha.pa.us

------------------------------