Return to Question

This question has gotten a lot of attention on SO:
Sorting 1 million 8-digit numbers in 1MB of RAM

The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\mathord{,}999\mathord{,}999]$) using only 1 MB of memory ($2^{20}$ bytes = $2^{23}$ bits) and no external storage. The program must read values from an input stream and write the sorted result to an output stream.

Obviously the entire input can't fit into memory, but clearly the result can be represented in under 1 MB since $2^{23} \geq \log_2 \binom{10^8}{10^6} \approx 8079302$ (it's a tight fit).

So, what is the minimum amount of space needed to sort n integers with duplicates in this streaming manner, and is there an algorithm to accomplish the specified task?

This question has gotten a lot of attention on SO:
Sorting 1 million 8-digit numbers in 1MB of RAM

The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\mathord{,}999\mathord{,}999]$) using only 1 MB of memory ($2^{20}$ bytes = $2^{23}$ bits) and no external storage. The program must read values from an input stream and write the sorted result to an output stream.

Obviously the entire input can't fit into memory, but clearly the result can be represented in under 1 MB since $2^{23} \geq \log_2 \binom{10^8}{10^6} \approx 8079302$ (it's a tight fit).

So, what is the minimum amount of space needed to sort n integers with duplicates in this streaming manner, and is there an algorithm to accomplish the specified task?

This question has gotten a lot of attention on SO:
Sorting 1 million 8-digit numbers in 1MB of RAM

The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\mathord{,}999\mathord{,}999]$) using only 1 MB of memory ($2^{20}$ bytes = $2^{23}$ bits) and no external storage. The program must read values from an input stream and write the sorted result to an output stream.

Obviously the entire input can't fit into memory, but clearly the result can be represented in under 1 MB since $2^{23} \geq \log_2 \binom{10^8}{10^6} \approx 8079302$ (it's a tight fit).

So, what is the minimum amount of space needed to sort n integers with duplicates in this buffered manner, and is there an algorithm to accomplish the specified task?

This question has gotten a lot of attention on SO:
Sorting 1 million 8-digit numbers in 1MB of RAM

The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\mathord{,}999\mathord{,}999]$) using only 1 MB of memory ($2^{20}$ bytes = $2^{23}$ bits) and no external storage. The program must read values from an input stream and write the sorted result to an output stream.

Obviously the entire input can't fit into memory, but clearly the result can be represented in under 1 MB since $2^{23} \geq \log_2 \binom{10^8}{10^6} \approx 8079302$ (it's a tight fit).

So, what is the minimum amount of space needed to sort n integers with duplicates in this streaming manner, and is there an algorithm to accomplish the specified task?

This question has gotten a lot of attention on SO:

 http://stackoverflow.com/questions/12748246/sorting-1-million-8-digit-numbers-in-1mb-of-ram

The problem is to sort a stream of 1 million 8-digit numbers using only 1 MB of memory ($2^{20}$ bits) and no external storage. The program must read values from an input stream and write the sorted result to an output stream.

Obviously the entire input can't fit into memory, but clearly the result can be represented in under 1 MB since $2^{20} \geq \log_2( \textstyle\left(\!\!{10^8 \choose 10^6}\!\!\right))$.

So, what is the minimum amount of space needed to sort n integers with duplicates in this buffered manner, and is there an algorithm to accomplish the specified task?

This question has gotten a lot of attention on SO: 
Sorting 1 million 8-digit numbers in 1MB of RAM

The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\mathord{,}999\mathord{,}999]$) using only 1 MB of memory ($2^{20}$ bytes = $2^{23}$ bits) and no external storage. The program must read values from an input stream and write the sorted result to an output stream.

Obviously the entire input can't fit into memory, but clearly the result can be represented in under 1 MB since $2^{23} \geq \log_2 \binom{10^8}{10^6} \approx 8079302$ (it's a tight fit).

So, what is the minimum amount of space needed to sort n integers with duplicates in this buffered manner, and is there an algorithm to accomplish the specified task?