Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!julius.cs.uiuc.edu!apple!agate!shelby!neon!pescadero.Stanford.EDU!philip
From: philip@pescadero.Stanford.EDU (Philip Machanick)
Newsgroups: comp.sys.mac.programmer
Subject: Fast sorts
Message-ID: <1990Dec24.204236.4231@Neon.Stanford.EDU>
Date: 24 Dec 90 20:42:36 GMT
Sender: news@Neon.Stanford.EDU (USENET News System)
Reply-To: philip@pescadero.stanford.edu
Organization: Computer Science Department, Stanford University
Lines: 26

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