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

Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM by Daniel_Newby on Sunday October 21, 2012 @06:10PM (#4681010)

"The list of numbers may contain duplicates, which I must not discard."

[ Parent | on HN ]

Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM by alecco on Sunday October 21, 2012 @06:16PM (#4681024)

I guess the googlers woud answer having "0:1" for duplicates.

Big problem #1: insertions for 1M integers would take ages.

Big problem #2: And some distributions can't be covered this way. For example, 1m integers with distances 0:99 (e.g. +99 each one). Now think the same but with random distance in the range of 0:99. (Note 99999999/1000000 = 99.99, so it's possible input)

Google's approach is nonsense, too.

[ Parent | on HN ]