Article View: comp.lang.misc
Article #2026Re: A very brief history of optimal sorting methods
From: Dan Bernstein
Date: Mon, 12 Nov 1990 18:54
Date: Mon, 12 Nov 1990 18:54
17 lines
1103 bytes
1103 bytes
In article <4248@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > For practical purposes, radix sort of machine integers may be taken as > linear in the number of bytes, because the range of values is fixed. You imply that this is not true for theoretical purposes. You are wrong. Sorting is linear in the number of bytes being sorted. This is true both theoretically and practically. > (A crude radix sort would not do for languages like Lisp, Scheme, Pop, and > some Prologs A *crude* radix sort would not do for any serious application. A *good* radix sort is linear in the number of bytes being sorted. ---Dan
Technical Details
Message-ID:
<24945:Nov1218:54:5590@kramden.acf.nyu.edu>Path:
arc1-ca.pugleaf.net!utzoo!attcan!uunet!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstndReferences:
<6913:Nov1008:23:5690@kramden.acf.nyu.edu> <237@smds.UUCP> <4248@goanna.cs.rmit.oz.au>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!attcan!uunet!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: <24945:Nov1218:54:5590@kramden.acf.nyu.edu> Date: 12 Nov 90 18:54:55 GMT References: <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <237@smds.UUCP> <4248@goanna.cs.rmit.oz.au> Organization: IR Lines: 17