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 (8388608 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 sorted result can be represented in under 1 MB since $8388608 >= \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?