Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM
by jules on Monday October 22, 2012 @01:23PM
(#4684231)
Sure, if you encode cleverly. That is the essential difficulty of the problem which he glosses over (note that he explicitly says that he will store the differences as 4 byte numbers). Getting it under 1.5MB (or even 1.1MB) is probably easy, but I have yet to see an encoding which is sufficiently compact to fit in 1MB.
Right.
and you'll end up with 8 bytes x 10^6 = 7.6 megabytes.
Not if you encode cleverly. The successive differences will be on the scale of 10^8/10^6 = 100, which is a very small number. It takes 7 bits to store, or at least 8 bits in a variable-width encoding.