Return to 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.

(I think I can see how to do it but I won't give my answer for a while.)

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.

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.

(I think I can see how to do it but I won't give my answer for a while.)

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.

(I think I can see how to do it but I won't give my answer for a while.)

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.

(I think I can see how to do 2 lists, but $k$ lists is harder.)

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.

(I think I can see how to do it but I won't give my answer for a while.)