All of these bizzaro explanations leave me wondering if I've missed something. Can't this be elegantly solved via the pigeonhole principle?

There are one million numbers to be sorted, out of a space of one hundred million. That means that no number may be more than 100 away from any other number once fully sorted (7 bits). Therefore, you can simply use deltas to encode your numbers, as 7 bit deltas * one million numbers < 1 MB RAM.

EDIT: should've been clearer: no number may be more than 100 away from any other number on average once fully sorted. Therefore, it's an average of 7 bits per number, maximum. Duplicates are even easier, since it's only one bit to encode the duplicate (a delta of zero).

EDIT 2: As for the encoding to be used, I think a universal code or Golomb code would probably be sufficient. They can get quite close to natural entropy.