Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!mcnc!uvaarpa!haven!adm!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: A very brief history of optimal sorting methods
Message-ID: <6913:Nov1008:23:5690@kramden.acf.nyu.edu>
Date: 10 Nov 90 08:23:56 GMT
References: <24149:Nov905:42:0990@kramden.acf.nyu.edu> <5488@lanl.gov>
Organization: IR
Lines: 40

This is funny. Computer science really does progress backwards.

In the '60s, people knew that sorting was linear in the number of bytes
being sorted. The post office had already been using MSD radix sort for
a long time, though they probably never bothered to analyze its running
time. Knuth says that LSD became more popular for computers because in
MSD ``the multiplicity of piles becomes confusing''; others pointed
wisely to the initials LSD and smiled.

In 1987, Tarjan et al. appeared on the sorting scene, with their ``new
partitioning algorithms.'' That's right: sorting in linear time. With
what? MSD radix sort. Hey, I'm impressed.

Last year, somebody or other appeared on the sorting scene. Guess what?
An o(n log n) sort. This one wasn't linear, though; it wasn't even
practical. It used all sorts of weird bit manipulations to ``break the
sorting barrier.'' Something like n log n/log log n. Computer scientists
around the world began teaching courses on this huge advance. (No joke.)

Now Jim Giles appears on the sorting scene. Guess what? Radix sorts are
slower than n log n. n log n is a lower bound.

I thank God for not making me a computer scientist.

Luckily, on the other side of the fence, we programmers still know that
sorting is linear. Thanks to Keith Bostic, a nicely cleaned up version
of my linear-time radix sort code will appear in the BSD 4.4 library.

In article <5488@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
  [ there aren't linear-time sorts, everything's O(n log n) ]
> That's why I didn't bother to answer
> your next post - you didn't seem to realize that an Nlog(N) sort is
> _faster_ than a 'linear' radix sort when the keyspace is sparcely
> filled.)

The sort program I plan to contribute to Berkeley runs more than twice
as fast as the AT&T-derived version, which I presume uses a merge sort
or some other n log n method. Believe what you want to, Jim.

---Dan