Path: utzoo!attcan!uunet!samsung!sdd.hp.com!wuarchive!psuvax1!news
From: flee@guardian.cs.psu.edu (Felix Lee)
Newsgroups: comp.std.c
Subject: Re: qsort(), bsearch(), and rude comparison functions
Message-ID: <Fz+kg#m2@cs.psu.edu>
Date: 10 Oct 90 08:05:48 GMT
References: <1990Oct6.013443.5364@twinsun.com>
	<1990Oct9.062455.21197@sq.sq.com> <Fex+yrm2@cs.psu.edu>
	<1990Oct9.231612.10881@nntp-server.caltech.edu>
Sender: news@cs.psu.edu (Usenet)
Organization: Penn State Computer Science
Lines: 11
Nntp-Posting-Host: guardian.cs.psu.edu

I spoke hastily.  Even if comparison is random, any reasonable sorting
algorithm "makes progress" and will do no more than the worst-case
number of comparisons.

qsort() in 4.3 BSD however will have a decent chance of running past
the bounds of the array in its final insertion sort pass.  Here's a
pathological comparator that guarantees this behavior:
	int cmp(a, b) char * a; char * b;
	{ return b - a; }
--
Felix Lee	flee@cs.psu.edu