Article View: comp.lang.misc
Article #2021Re: A very brief history of optimal sorting methods
From: Richard Harter
Date: Mon, 12 Nov 1990 07:35
Date: Mon, 12 Nov 1990 07:35
19 lines
1482 bytes
1482 bytes
In article <16709:Nov1113:56:2390@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > 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. One time only, I'll try to make it very simple. If you do a radix sort you make multiple passes over the data. In each pass you move all of the records. The minimum number of passes needed is log(N) where N is the number of records and the base of the logarithm is the bin size. N*log(N) records must be moved. Is that clear enough? -- Richard Harter, Software Maintenance and Development Systems, Inc. Net address: jjmhome!smds!rh Phone: 508-369-7398 US Mail: SMDS Inc., PO Box 555, Concord MA 01742 This sentence no verb. This sentence short. This signature done.
Technical Details
Message-ID:
<237@smds.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!samsung!crackers!jjmhome!smds!rhReferences:
<5488@lanl.gov> <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <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!clyde.concordia.ca!uunet!samsung!crackers!jjmhome!smds!rh From: rh@smds.UUCP (Richard Harter) Newsgroups: comp.lang.misc Subject: Re: A very brief history of optimal sorting methods Summary: Crank computer science Message-ID: <237@smds.UUCP> Date: 12 Nov 90 07:35:22 GMT References: <5488@lanl.gov> <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <16709:Nov1113:56:2390@kramden.acf.nyu.edu> Organization: SMDS Inc., Concord, MA Lines: 19