Path: 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

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