Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!rpi!sci.ccny.cuny.edu!phri!cmcl2!kramden.acf.nyu.edu!brnstnd From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.lang.misc Subject: Re: A very brief history of optimal sorting methods Message-ID: <761:Nov2707:26:3590@kramden.acf.nyu.edu> Date: 27 Nov 90 07:26:35 GMT References: <4371@goanna.cs.rmit.oz.au> Organization: IR Lines: 35 In article mwm@fenris.relay.pa.dec.com (Mike (My Watch Has Windows) Meyer) writes: > In article <4371@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > Let me paraphrase this: > Dan Bernstein: you can run faster if you don't wear blinkers > Mike Meyer: prove it wearing these blinkers > Oh, horse pucky. If the sorting method in question can't be turned > into one of the two options I list, then it's basically worthless. I have to agree with Mike here: if a supposedly general sorting method can't at least be used to implement sort(1) (efficiently), it's pointless. > As for at the code Dan let me have, it's a very well-designed (and, > for the most part, written) MSD radix sort. As such, it will indeed > sort arbitrary strings with termination bytes in time linear in the > number of bytes to sort. In it's current form, it can't be used to > sort records with fixed-length keys holding arbitrary data. Well, yeah, I'm still working on it. I'll make the final sort(1) clone available ASAP. The right way to apply radix sort (or, in fact, almost any other sort) to your fixed-length records or other data structures inside a generic program is as follows: 1. Extract out of the structures some lexically ordered key. Append to each key some index to the original structure, or the entire original structure. 2. Apply radixsort() to the keys. 3. Sweep through the sorted keys, reordering the structures. You can use escape characters (255 1 represents 255, 255 2 represents 0) to handle the limited character set. ---Dan