Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!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: <4440:Nov1405:06:2590@kramden.acf.nyu.edu>
Date: 14 Nov 90 05:06:25 GMT
References: <16709:Nov1113:56:2390@kramden.acf.nyu.edu> <5812@lanl.gov>
Organization: IR
Lines: 18

In article <5812@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> From article <16709:Nov1113:56:2390@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> > Models of computation are cute, but I live in the real world.
> So do I.  In the real world, keys are almost _never_ just one byte
> long.

Sorting is linear in the number of bytes being sorted. The length of the
keys is absolutely, entirely irrelevant to this conclusion.

> The log n factors implicit in radix sorts _do_ exist for any
> keyspaces that are above the 'toy' level.

In the very common case that keys are not all distinct, radix sort can
be asymptotically FASTER than n log n, depending on the amount of
repetition. The ``implicit'' factor that all you computer scientists
keep imagining does NOT exist.

---Dan