Too large in memory
You want to sort a list of a number of integers. Let's call the number of integers that will arrive to be \(n\), even though you don't know what its value. A special property of this list is that all of them are different, and they all are in the range \([0, n]\). The list will be delivered online (that is, you only have access to the next item in the list). You also know that the list is huge, so holding the entire list in your memory would be a big problem; you want to keep the memory used as low as possible. How much additional memory do you need?
Details and Assumptions:
Your program has access to an input and an output (input is read-only and output is write-only). Your program can request the next number in the list from the input, and your program can print a number to the output; both of them don't require any additional memory except what you use to store the number read/written. You don't know the number of integers that will arrive; when you read
-1, it means the input has stopped. You must print the integers to the output in the order you wish (that is, sorting them, from smallest to largest). Memory used is measured in the most number of bits used at once during the runtime of your program.