Sorting 1 million 8-digit decimal numbers in 1MB of RAM

Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM by jules on Monday October 22, 2012 @06:17AM (#4682469)

With 10^6 random numbers between 0 and 10^8 almost all operations will be splits, and you'll end up with 8 bytes * 10^6 = 7.6 megabytes. So indeed the chances of this working for a random sequence are extremely slim. You have to have a huge number of coalesces, which is just extremely unlikely when you choose 10^6 random numbers in a range of 10^8. So for almost all inputs this method doesn't work.

I simulated it with a Python program and you get about 10^4 coalesces. That doesn't even begin to make a dent in 10^6, and storing this will still take ~7 megabytes.

[ Parent | on HN ]

Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM by uvdiv on Monday October 22, 2012 @09:27AM (#4683014)

With 10^6 random numbers between 0 and 10^8 almost all operations will be splits,

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.

[ Parent | on HN ]

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.

[ Parent | on HN ]