Merge Two Sorted Hands

Let’s start with a pack of playing cards. Imagine you and your friend are playing a card game and at the end of the game, each of you has a hand of cards that is sorted. The hands do not have to be the same size, but for simplicity let’s say each of you has 26 cards. Now you want to merge them to get your original 52-card deck back. How would you do that?

One way is to put the cards from both hands into a pile and sort them using insertion sort. This is a valid way to merge the two sorted hands, but it does not take advantage of the fact that the two hands are already sorted. In fact, you could each shuffle your hand before putting them together, and it would not make any difference to the (asymptotic) running time of insertion sort. (In practice, it would make it worse, since the best case for insertion sort is when the input is already sorted, and shuffling would make it less likely to be sorted.)

But there is a better way to merge the two sorted hands. Imagine we lay out the two hands one above the other:

        ┌ S ┐   ┌ S ┐         ┌ C ┐         ┌ H ┐
Hand 1: │   │   │   │         │   │         │   │
        └ A ┘ , └ 3 ┘ , ... , └ 9 ┘ , ... , └ 2 ┘
        ┌ S ┐   ┌ S ┐         ┌ C ┐         ┌ H ┐
Hand 2: │   │   │   │         │   │         │   │
        └ 2 ┘ , └ 5 ┘ , ... , └ 3 ┘ , ... , └ K ┘

Now let’s try to build the original deck one card at a time. Look at the first card in each hand. The smaller one is the Ace of spades, so we take it out and put it in the first position of the original deck.

        ┌ S ┐         ┌ C ┐         ┌ H ┐
Hand 1: │   │         │   │         │   │
        └ 3 ┘ , ... , └ 9 ┘ , ... , └ 2 ┘
        ┌ S ┐   ┌ S ┐         ┌ C ┐         ┌ H ┐
Hand 2: │   │   │   │         │   │         │   │
        └ 2 ┘ , └ 5 ┘ , ... , └ 3 ┘ , ... , └ K ┘
Deck:   ┌ S ┐
        │   │
        └ A ┘

Now look at the first card in each hand again. The smaller one is the 2 of spades, so we take it out and put it in the second position of the original deck.

        ┌ S ┐         ┌ C ┐         ┌ H ┐
Hand 1: │   │         │   │         │   │
        └ 3 ┘ , ... , └ 9 ┘ , ... , └ 2 ┘
        ┌ S ┐         ┌ C ┐         ┌ H ┐
Hand 2: │   │         │   │         │   │
        └ 5 ┘ , ... , └ 3 ┘ , ... , └ K ┘
Deck:   ┌ S ┐   ┌ S ┐
        │   │   │   │
        └ A ┘ , └ 2 ┘

We repeat this process until both hands are empty. At the end, we will have the original deck back, and it will be sorted. I want you to pause and convince yourself that this process will work! Feel free to get out a pack of cards and try it out.

Now count the work. At each step we compare the first card in each hand, and then we move one of them out of its hand and into the deck. So each of the 52 cards is placed exactly once, and once it is placed we never look at it again. That is 52 steps.

Insertion sort on the combined pile does much more than that. A single card there can be shifted past many other cards before it reaches its final position, and we saw that adds up to a quadratic number of moves. When we merge, we never shift a card past another card.