Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM
by greendestiny on Sunday October 21, 2012 @09:13PM
(#4681431)
Yeah I think if you number the permutations in order from smallest to largest (ie all 0 to all 99999999) then you can update as new numbers come in by keeping track of the number (N) you've already seen and assume the other (million - N) are 0. So you just have your 10^6 bit number representing the sorted list of numbers and an 27bit integer representing the number of samples seen. The update function might be a bit ugly though :)
It's probably actually a question of whether the update function could be done in the remaining memory - it certainly couldn't unpack the whole representation.
It's probably actually a question of whether the update function could be done in the remaining memory - it certainly couldn't unpack the whole representation.