Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <4248@goanna.cs.rmit.oz.au>
Date: 12 Nov 90 11:54:14 GMT
References: <5488@lanl.gov> <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <237@smds.UUCP>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 30

In article <237@smds.UUCP>, rh@smds.UUCP (Richard Harter) writes:
> 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.

> One time only, I'll try to make it very simple.

It is worth noting, however, that for a *fixed* range of integers [a,b],
a record is ceil(lg(b-a+1)) bits (call that lg(M)), the entire collection
of records is O(N*lg(M)) bits, and if we sort K bits at a time, we require
ceil(lg(M)/K) passes, each pass of which is linear in the number of bytes
being sorted.  Consider an array of N 32-bit integers, where we take 8-bit
"digits".  (Not wholly unrealistic.)  Then we need a maximum of 4 passes.

So if you want to sort an array of Pascal 'integer's, C 'long's,
Fortran 'INTEGER*4's, and so on, it's going to take you at most 4 passes.
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.

The studies which have allegedly shown quicksort to be fast have considered
sorting hardware integers.  For that special case, quicksort is O(N**2) and
radix sort is O(N), and a fairly crude radix sort can make quicksort look
very sick indeed.

(A crude radix sort would not do for languages like Lisp, Scheme, Pop, and
some Prologs which don't impose arbitrary and to-the-user unmotivated
limits on the size of integers.)

-- 
The problem about real life is that moving one's knight to QB3
may always be replied to with a lob across the net.  --Alasdair Macintyre.