Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM
by danbruc on Sunday October 21, 2012 @04:31PM
(#4680712)
There is not enough memory to keep all the numbers and therefore radix sort is no viable solution. But I think you actually meant counting sort, but this will not work either. It requires 100,000,000 slots each 20 bits wide for a total of almost 238.5 MiB.
Depending on his dataset characteristics a radix sort can have a space requirement as low as a few hundred bytes to sort several million values.
EG: 8-bit values, Simply make a 256byte array. Increase the appropriate count on each value when you see a value. When you've gone through the list, loop through the array outputting count values at that index. It's also quite cache friendly, mind the last time I compared was on a Pentium PRO to quick sort.
For larger datasets, you actually want to compare on the digits (LSD or MSD first), and that'll take more memory.
EDIT: Originally posted that it'd take 256 bytes of memory. That's not true for his dataset.