Path: utzoo!attcan!uunet!nih-csl!lhc!adm!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: <16709:Nov1113:56:2390@kramden.acf.nyu.edu>
Date: 11 Nov 90 13:56:23 GMT
References: <5488@lanl.gov> <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <235@smds.UUCP>
Organization: IR
Lines: 16

In article <235@smds.UUCP> rh@smds.UUCP (Richard Harter) writes:
> In article <6913:Nov1008:23:5690@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> > 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.
> If you have N records with distinct keys the effective length of the
> keys is log(N).
  [ several sentences of similar handwaving deleted ]
> THERE ARE NO TRULY LINEAR SORTS.

Sorting is linear in the number of bytes being sorted. Feel free to
spout on about implicit log n factors that don't exist; I'll continue to
sort n-byte files in time between bn and cn seconds for nonzero b and c.
Models of computation are cute, but I live in the real world.

---Dan