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$ largest numbers.

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

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 .