qsort (was Looking for portable sort algorithm)

[Chris Torek]

In article <5217 at merlin.usc.edu> jeenglis at nunki.usc.edu (Joe English) writes:
>As long as we're on the subject of sorting, I was
>wondering why the standard sort routine is implemented
>as a quick-sort nearly everywhere, given its poor
>worst-case behaviour.  Any guesses?

If true: laziness.  If not: well, no answering `why' for a question
that is false.  (qsort simply means `apply some reasonably fast sort',
not `apply quicksort'.  There is no reason someone could not put in all
sorts of sorts, selected automatically at runtime, perhaps.)  It is
worth noting that 4.3BSD uses a modified quick sort that (a) chooses
one of three for its partition element and (b) switches to an insertion
sort when the number of items in a partition is `small' (<= 10).  It
also does the larger partition using tail recursion (i.e., `goto') so
that the stack does not get as deep.  The `median of three' keeps
qsort from being worst-case on nearly sorted arrays.  The insertion
sort should be obvious.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris