You could use binary heap, so the compexity is O(n log k) and you get the final list immediatly.
First you put into heap first elements of the streams. Than you repeat the following step: extract minimal element from heap, add it to output stream and add next element from the stream to which the last extracted element from the heap belongs to.
