Sorting interleaved sorted lists

Question

By interleaving two lists I mean to combine them into a single list in any way that maintains the relative order of the elements coming from each list. For example, interleaving $(x_1,x_2,x_3)$ and $(y_1,y_2,y_3,y_4)$ might produce $(x_1,x_2,y_1,x_3,y_2,y_3,y_4)$ or $(y_1,x_1,y_2,y_3,x_2,y_4,x_3)$ or 33 other possibilities.

Now suppose you have a list and you know for sure that it was made by interleaving two sorted lists. However you don't know how long the two lists were, and you don't know in which way they were interleaved.

1. How quickly can you sort your list?

(Assume the list is in an array and comparisons and single-element reads and writes take unit time.)

2. What if your list was made by interleaving $k$ sorted lists?

The usual information-theoretic upper bound is $O(n)$ if $k=O(1)$. But how can $O(n)$ be achieved?

This question arises in practice (so someone should have considered it before). You have an incoming sorted stream of items and you want to output those satisfying some expensive predicate, so you feed them round-robin into $k$ independent testers running in parallel which each write their good items to the output. Now the output is an interleaving of $k$ sorted lists.

Answer 1

In both cases it should be easy to achieve the $O(n)$ bound.

First decompose the interweaved list $L$ into $k$ sorted lists $S_j$ ($j=1,\ldots,k$) by stepwise ($i=1,\ldots n$) appending $L_i$ to list $S_j$ if $L_i\geq\max (S_j)$ but $L_i<\max( S_{j+1})$ for $j<k$. This is always possible because by the assumption $L_i$ is always $\geq$ one of last $k$ partially largest numbers (in the sense given by the algorithm).

The $k$ sorted lists $S_j$ can then be interweaved into a single sorted list. All this is possible in $O(k\,n)$ steps .