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

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.