News for hackers. Stuff that matters.

A comment on Sorting 1 million 8-digit decimal numbers in 1MB of RAM . Parent comment

Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM by tolmasky on Sunday October 21, 2012 @02:29PM (#4680365)
Duplicates are allowed, so you could for example have 500,000 zeros and 500,000 99,999,999's, which are more than 100 apart.
[ Parent | on HN ]
Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM by codex on Sunday October 21, 2012 @11:14PM (#4681698)
That is one of the more ideal distributions, as each number gets one (zero) bit for delta, and the number at the jump point gets a large but globally inconsequential number of bits. Bits per number is still less than 7.
[ Parent | on HN ]