Tom Lane wrote:
>
> Doug McNaught <doug@wireboard.com> writes:
> > Actually, the C standard says nothing about what algorithm should be
> > used for qsort(); it's simply supposed to be a fast in-memory sort.
> > The qsort() name is just a historical artifact.
>
> In practice I believe qsort usually is a quicksort; it's just too good
> of a general-purpose algorithm. However you do need a good heuristic
> for selecting the median value to split on, or you can get burnt by
> corner cases. I'm guessing that Sun was careless and got burnt ...
quicksort is a pretty poor algorithm if your data is in some kind of order
already. If you are sorting a list that is mostly in the order in which you
want, it will perform very badly indeed. If you could choose the sorting
algorithm based on knowledge of the order of the data, it may improve
performance.
Data retrieved from an index scan is likely to be in some sort of order. If the
order of the data retrieved from an index scan is the same as the order to
which it will be sorted at a later stage of the query, quicksort will probably
be worse than something like shell sort.