Article View: comp.lang.misc
Article #2038Re: A very brief history of optimal sorting methods
From: Jim Giles
Date: Tue, 13 Nov 1990 20:36
Date: Tue, 13 Nov 1990 20:36
12 lines
1038 bytes
1038 bytes
From article <16709:Nov1113:56:2390@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein): > [...] > 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. So do I. In the real world, keys are almost _never_ just one byte long. The log n factors implicit in radix sorts _do_ exist for any keyspaces that are above the 'toy' level. J. Giles
Technical Details
Message-ID:
<5812@lanl.gov>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!sdd.hp.com!uakari.primate.wisc.edu!uflorida!haven!adm!cmcl2!lanl!jlgReferences:
<16709:Nov1113:56:2390@kramden.acf.nyu.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!sdd.hp.com!uakari.primate.wisc.edu!uflorida!haven!adm!cmcl2!lanl!jlg From: jlg@lanl.gov (Jim Giles) Newsgroups: comp.lang.misc Subject: Re: A very brief history of optimal sorting methods Message-ID: <5812@lanl.gov> Date: 13 Nov 90 20:36:36 GMT References: <16709:Nov1113:56:2390@kramden.acf.nyu.edu> Organization: Los Alamos Natl Lab, Los Alamos, N.M. Lines: 12