philip@pescadero.Stanford.EDU (Philip Machanick) (12/25/90)
I seem to recall a thread about fast sorts on this group a while back. I recently coded a sort which seems to have some useful advantages: o requires minimal (bounded by a constant) extra space o linear time, as long as the size of keys is constant o simple to code o despite extra overhead (and no real attempt at optimizing) as fast as bubblesort on small data sets (around 100 - below this, too fast to measure easily using tickCount) o won't do swaps on already sorted data Drawbacks: o dependent on representation of keys (my version only works for positive integers, could adapt to strings, signed integers easily; floating point a bit more difficult) o machine-dependent because of the dependence on representation of keys A more general version, working around these limitations, would probably not be a huge amount slower, though special-casing to each data type / representation would be fastest. In my tests, it takes 1.5s to sort 10000 random positive integers on my IIci. How does this compare with other sorts? -- Philip Machanick philip@pescadero.stanford.edu
amanda@visix.com (Amanda Walker) (12/27/90)
Sounds like you may have reinvented the radix sort, or a variation. Care to post the algorithm? Not handling variable-length keys could be a problem, although it's what reminds me of a radix sort. -- Amanda Walker amanda@visix.com Visix Software Inc. ...!uunet!visix!amanda -- Marching to a different kettle of fish.