Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!uhccux!munnari.oz.au!cs.mu.oz.au!ok From: ok@cs.mu.oz.au (Richard O'Keefe) Newsgroups: comp.lang.modula2 Subject: Re: Sorts Message-ID: <2074@munnari.oz.au> Date: 10 Sep 89 11:01:42 GMT References: Sender: news@cs.mu.oz.au Lines: 22 In article , MARKV@UKANVAX.BITNET ("MARK GOODERUM - UNIV. OF KANSAS ACS - MARKV@UKANVAX") writes: > I have a couple of Quicksort routines lying around that > aren't too bad and will give you much better performance than the old > quick and dirty bubble sorts. *WARNING* If your comparisons are costly (e.g. comparing strings, or almost _anything_ more than a single in-line numeric comparison), Quicksort was known to do 40% more comparisons than Merge sort _when_ _it_ _was_ _invented_. It was invented for a machine whose main memory was something like 512 words (its disc was a massive 16k words), so that minimal extra space was vital. If you have room for one extra word per record (and if you are using variable length records you are almost certainly using a link word of some sort anyway) then the space advantage vanishes. Even with the median-of-three hack, the average case of "Quick" sort is slower than the *worst* case of merge sort. If you are sorting numbers, radix sort is _grossly_ faster than "quick" sort. I have posted some sorting routines in C to the original requester. (I accidentally posted them to MARKV too, sorry 'bout that.) Bubble sort? Surely nobody has ever used bubble sort except as an example in a textbook of how badly it is possible to do it.