🚀 go-pugleaf

>	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).

Only trouble is that it's O(k), not O(n), because that's how long
it takes to scan all the way through your BIG memory.

When k is much larger than n, you can sort in O(n log(k)/R) by doing a
radix sort in radix R.