Repeating the Merge Process

Let me show you an idea. Here is an array of integers:

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  6  │  5  │  2  │  0  │  9  │  1  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘

Let’s take every pair of adjacent elements and merge them following the merge process we just went over:

• Merge 6 and 5 to get [5, 6]
• Merge 2 and 0 to get [0, 2]
• Merge 9 and 1 to get [1, 9]
• 3 is not merged since it does not have a pair

Here is the resulting array:

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  5  │  6  │  0  │  2  │  1  │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
     └──┬──┘     └──┬──┘     └──┬──┘     │
        ▼           ▼           ▼        ▼
      sorted     sorted       sorted   sorted

Notice that I consider the single-element subarray 3 to be sorted as well, since an array (or in this case, a subarray) with one element is always sorted. In fact, from the start I could think of the problem this way: we have an array of $n$ elements, and we can think of it as $n$ subarrays of length $1$, and each of these subarrays is sorted. Then we can merge adjacent pairs of these subarrays to get about $n/2$ sorted subarrays of length (at most) $2$.

Before:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  6  │  5  │  2  │  0  │  9  │  1  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
     │     │     │     │     │     │     │
     ▼     ▼     ▼     ▼     ▼     ▼     ▼
     ✓     ✓     ✓     ✓     ✓     ✓     ✓

After:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  5  │  6  │  0  │  2  │  1  │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
     └──┬──┘     └──┬──┘     └──┬──┘     │
        ▼           ▼           ▼        ▼
        ✓           ✓           ✓        ✓

Now let’s repeat the process. We can merge adjacent pairs of these sorted subarrays to get about $n/4$ sorted subarrays of length (at most) $4$:

• Merge [5, 6] and [0, 2] to get [0, 2, 5, 6]
• Merge [1, 9] and [3] to get [1, 3, 9]

Here is the resulting array:

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  0  │  2  │  5  │  6  │  1  │  3  │  9  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
     └────────┬────────┘     └─────┬─────┘
              ▼                    ▼
            sorted               sorted

Finally, we can merge the two sorted subarrays to get a fully sorted array:

• Merge [0, 2, 5, 6] and [1, 3, 9] to get [0, 1, 2, 3, 5, 6, 9]

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  0  │  1  │  2  │  3  │  5  │  6  │  9  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
     └─────────────────┬──────────────────┘
                       ▼
                    sorted