Sorry, I was paraphrasing the question and not giving every detail that I received. They also stated that there are no gaps, the values increment by one, and start at zero.
The data itself is ordered (which is why the task is to print them in order), but the order you receive the values is can happen in any order (ie the processing was split into multiple threads and each thread is posting back the results from the work).
Ah then that's the classic "merge k sorted streams" question. It's a good question and easy to solve in a coding interview. Good candidate should be able to solve in about 30 minutes. My favorite solution goes something like "put values in a heap and then read them back out" because you only need to read 1 value from each stream at a time.
If the input is infinite and unordered and the task is to produce output in order, how do you know when it’s OK to start writing output?