Merge Two Sorted Arrays

Let’s work out another example, this time with simple arrays of integers.

Imagine you have two sorted arrays of integers, and you want to merge them into a single sorted array. For example, if you have the arrays [1, 3, 5] and [2, 4, 6, 7], you want to merge them into [1, 2, 3, 4, 5, 6, 7].

   Array 1:             Array 2:
  ┌─────┬─────┬─────┐   ┌─────┬─────┬─────┬─────┐
  │  1  │  3  │  5  │   │  2  │  4  │  6  │  7  │
  └─────┴─────┴─────┘   └─────┴─────┴─────┴─────┘
                      ↓
   Merged Array:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘

Let’s define three pointers: i for the current index in the first array, j for the current index in the second array, and k for the current index in the merged array. We will start with all three pointers at 0.

   Array 1:             Array 2:
  ┌─────┬─────┬─────┐   ┌─────┬─────┬─────┬─────┐
  │ ░1░ │  3  │  5  │   │ ░2░ │  4  │  6  │  7  │
  └─────┴─────┴─────┘   └─────┴─────┴─────┴─────┘
    i=0                   j=0

   Merged Array:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │     │     │     │     │     │     │     │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
    k=0

We compare the elements at i and j. The smaller one is 1, so we put it in the merged array at index k, and then we move the pointer i to the next index in the first array, and move k to the next index in the merged array.

   Array 1:             Array 2:
  ┌─────┬─────┬─────┐   ┌─────┬─────┬─────┬─────┐
  │ █1█ │ ░3░ │  5  │   │ ░2░ │  4  │  6  │  7  │
  └─────┴─────┴─────┘   └─────┴─────┴─────┴─────┘
          i=1             j=0

   Merged Array:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  1  │     │     │     │     │     │     │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
          k=1

Now we compare the elements at i and j again. The smaller one is 2, so we put it in the merged array at index k, and then we move the pointer j to the next index in the second array, and move k to the next index in the merged array.

   Array 1:             Array 2:
  ┌─────┬─────┬─────┐   ┌─────┬─────┬─────┬─────┐
  │ █1█ │ ░3░ │  5  │   │ █2█ │ ░4░ │  6  │  7  │
  └─────┴─────┴─────┘   └─────┴─────┴─────┴─────┘
          i=1                   j=1

   Merged Array:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  1  │  2  │     │     │     │     │     │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
                k=2

We repeat this. 3 comes from the first array, then 4 from the second, then 5 from the first. At that point i has reached 3, which is past the end of the first array:

   Array 1:             Array 2:
  ┌─────┬─────┬─────┐   ┌─────┬─────┬─────┬─────┐
  │ █1█ │ █3█ │ █5█ │   │ █2█ │ █4█ │ ░6░ │  7  │
  └─────┴─────┴─────┘   └─────┴─────┴─────┴─────┘
                   i=3                j=2

   Merged Array:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  1  │  2  │  3  │  4  │  5  │     │     │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
                                  k=5

The comparison rule does not apply here. There is no element at i to compare against, because we have already placed every element of the first array. But we do not need one. Everything left in the second array is already sorted, and it is all at least as large as everything we have placed so far. So we copy the rest of the second array into the merged array, 6 and then 7, and the merged array is complete.