Article View: comp.lang.misc
Article #2017Re: A very brief history of optimal sorting methods
From: Dan Bernstein
Date: Sun, 11 Nov 1990 13:56
Date: Sun, 11 Nov 1990 13:56
16 lines
1238 bytes
1238 bytes
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
Technical Details
Message-ID:
<16709:Nov1113:56:2390@kramden.acf.nyu.edu>Path:
arc1-ca.pugleaf.net!utzoo!attcan!uunet!nih-csl!lhc!adm!cmcl2!kramden.acf.nyu.edu!brnstndReferences:
<5488@lanl.gov> <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <235@smds.UUCP>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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