🚀 go-pugleaf

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 |
+---------------------------+------------------+-------------+