🚀 go-pugleaf

In article <600@sdcc12.UUCP> wa263@sdcc12.UUCP (bookmark) writes:
>
>	I know one really good use for a BIG core memory.  There is a
>simple O(n) sorting algorithm... suppose we want to sort n elements with
>keys ranging in value from 1 to k (k >= n).  Just get a big array of k
>slots, mark them all with some illegal value, then copy each of the items
>to be sorted into the appropriate (k'th) place in the array (this is
>called an "address calculation" sort).  Then scan the array through and
>copy out the items in order.  The sort phase is O(n), and the scan phase
>takes about constant+(n*otherconst) time, so the whole thing is O(n).

   The 'scan phase' takes ** O(k) ** time, not O(n).  In typical sorting
applications k >>> n.  If k ~ n, then we already have enough memory for
the size k table (if we have enough memory to quicksort the items them-
selves!).

   -- David desJardins