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

Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM by damienkatz on Sunday October 21, 2012 @01:23PM (#4680152)

Since no computational bound has been placed, this problem could be solved in n^2 by an insertion sort and keeping the list of numbers sorted in memory as they are received. Then the problem then boils down to encoding a list of sorted 8 digit decimal #s, where it's possible to insert new #s.

Since the #s are stored sorted and bounded in size, they can be encoded as deltas which will be more space efficient than storing absolute values. Now we just need to figure out the worst case encoding and will 1 million values fit?

[ Parent | on HN ]

Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM by andrewcooke on Sunday October 21, 2012 @07:39PM (#4681213)

i think that's the clearest answer i've seen. really, it's pretty much equivalent to the other answers, but at least for me it's by far the easiest to grasp. although i guess that may be because the idea is simply becoming familiar after reading the others.

the best "high level" explanation, i think, is that you are compressing the sorted numbers, which are therefore not random, and so concerns about the incompressibility of random streams are completely irrelevant.

[ Parent | on HN ]

Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM by eru on Monday October 22, 2012 @12:50PM (#4684054)

Merge sort would work better. But yes, the secret sauce is in the compression, not the sorting.

[ Parent | on HN ]