Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!rutgers!haven!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.c
Subject: qsort (was Looking for portable sort algorithm)
Keywords: C, sort algorithm, portable, wanted
Message-ID: <19708@mimsy.UUCP>
Date: 21 Sep 89 09:51:37 GMT
References: <1102@lakesys.UUCP> <3994@ncsuvx.ncsu.edu> <5217@merlin.usc.edu>
Distribution: na
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 20

In article <5217@merlin.usc.edu> jeenglis@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@mimsy.umd.edu	Path:	uunet!mimsy!chris