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?
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.
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?