Path: csiph.com!x330-a1.tempe.blueboxinc.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail NNTP-Posting-Date: Tue, 17 May 2011 14:00:15 -0500 Message-ID: <4DD2C5BF.5CB0@mindspring.com> Date: Tue, 17 May 2011 15:00:15 -0400 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.unix.programmer,comp.lang.c Subject: Re: Avoiding recursive stack overflow in C on Unix/Linux? References: <87r581ugbe.fsf@bazspaz.fatphil.org> <87iptbv3up.fsf@bazspaz.fatphil.org> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Lines: 34 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.154.223.204 X-Trace: sv3-bt7Wk+w6ivGpkPjAnJlmlNP1zw7x1w/ZgM390kjW4XfQOgwwmvikJwaTkCFJdAcOGvv8Jh2Ih4tK1SN!6KfBPueHbvFvBO1+4niTCetjXkoJLDDPer9e2cbUTQdXsIOpBv5c3Fk5HZQd7kQWyTpKMKqmfvQD!mW8holWrmn0= X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 2713 Xref: x330-a1.tempe.blueboxinc.net comp.unix.programmer:590 comp.lang.c:4175 robertwessel2@yahoo.com wrote: > > On May 17, 11:12 am, Keith Thompson wrote: > > Barry Margolin writes: > > > In article , > > > Keith Thompson wrote: > > [...] > > >> Quicksort is O(n log n) in the average case, > > >> O(N^2) in the worst case. > > A concrete question: Are there any existing C library > > implementations > > of qsort() that are vulnerable to this kind of problem? > Based solely on personal experience, I believe most C qsorts actually > implement some version of quicksort, and are vulnerable. A few do > introsort, and introsort is fairly common for C++ sort. I've also > seen one qsort that implemented heapsort* (which would not have the > issue). I think the issue is mainly history - most of the C > implementations have been around longer than introsort, and fall into > the if-it-ain't-broke category. > > *arguably a better general purpose choice than quicksort, but that’s a > different topic It's been a few years since I've looked at a library implementation of qsort, but not much more than a few years. I've seen some remarkably bad ones, and never a remarkably good one. -- pete