Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM
by hcles on Sunday October 21, 2012 @02:42PM
(#4680402)
> That means that no number may be more than 100 away from any other number once fully sorted (7 bits)
It's possible that 90% of numbers are <1 million, and the remaining 10% are > 91 million. That's a 90 million delta possibility.
[ Parent
| on HN ]
Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM
by Dylan16807 on Sunday October 21, 2012 @05:07PM
(#4680836)
You would of course use a delta scheme that can encode any number using O(log n) bits. At that point having a lopsided distribution of numbers actually helps you. Cramming the first 90% of the numbers into 1% of the space can save you about six bits per number. Even if you spread out the remaining 10% the price is going to be far less than sixty bits each.