Radix sort. Done. Depending on his dataset characteristics a radix sort can have a space requirement as low as a few hundred bytes to sort several million valu

Radix sort. Done. 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.