> That means that no number may be more than 100 away from any other number once fully sorted (7 bits)
It's possible that 90% of numbers are <1 million, and the remaining 10% are > 91 million. That's a 90 million delta possibility.
You would of course use a delta scheme that can encode any number using O(log n) bits. At that point having a lopsided distribution of numbers actually helps you. Cramming the first 90% of the numbers into 1% of the space can save you about six bits per number. Even if you spread out the remaining 10% the price is going to be far less than sixty bits each.
