Path: utzoo!mnetor!tmsoft!torsqnt!jarvis.csri.toronto.edu!rutgers!att!watmath!maytag!aries5!lhf
From: lhf@aries5 (Luiz H de Figueiredo)
Newsgroups: comp.lang.c
Subject: qsort
Message-ID: <860@maytag.waterloo.edu>
Date: 18 Nov 89 18:56:58 GMT
Sender: daemon@maytag.waterloo.edu
Reply-To: lhf@aries5 (Luiz H de Figueiredo)
Organization: Computer Systems Group, University of Waterloo
Lines: 20

In a recent thread about sorting strings, someone suggested that qsort was
not the way to go because quicksort is not very good for nearly ordered files.

My question is:
	Does qsort have to implement quicksort?

My point is that the *name* qsort is historical but qsort can actually be
very smart, eg. switching to insertion for small segments and/or pre-scan the
file (array) to avoid quadratic behaviour for sorted data.
In other words, qsort does not even have to implement quicksort at all!
What is more useful to assume is that qsort is *very* efficient, so that we
don't have to re-invent the wheel every day.

What does the standard say about this?


Luiz Henrique de Figueiredo		internet: lhf@aries5.uwaterloo.ca
Computer Systems Group			bitnet:   lhf@watcsg.bitnet
University of Waterloo
Waterloo, Ontario, Canada  N2L 3G1