Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!dsinc!netnews.upenn.edu!msuinfo!rang
From: rang@cs.wisc.edu (Anton Rang)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <RANG.90Nov18150047@nexus.cs.wisc.edu>
Date: 18 Nov 90 20:00:47 GMT
References: <5488@lanl.gov> <6913:Nov1008:23:5690@kramden.acf.nyu.edu>
	<16709:Nov1113:56:2390@kramden.acf.nyu.edu> <237@smds.UUCP>
Sender: news@msuinfo.cl.msu.edu
Organization: UW-Madison CS department
Lines: 30
In-Reply-To: rh@smds.UUCP's message of 12 Nov 90 07:35:22 GMT

Arrggh.  I know I'm going to regret getting into this thread.

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

  Are we assuming that the radix sort uses a fixed amount of auxiliary
storage?  If you sort using pointers, the time would be made up of:

  * The number of passes, which is at most the number of bytes/key;
      (replace 'byte' by a storage unit for your favorite base)
    Times the number of keys, since you're sorting all the records;
    Times the size of a pointer, since you're moving the pointers.

      This is O(bytes/key) * O(number of keys) * size of pointer.

      (If pointers are not fixed-length, this isn't linear; if they
      are, it's linear in the number of bytes.)

  * The time to rearrange records, which is obviously linear in the
    number of bytes.

Am I missing something here?  The original messages aren't on my news
system any more.  Is there an explanation of the algorithm being
discussed published somewhere?

	Anton
   
+---------------------------+------------------+-------------+
| Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison |
+---------------------------+------------------+-------------+