A Top-Down Trace

So far we have built sorted subarrays from the bottom up: single elements into pairs, pairs into fours, and so on. This time we start at the top, with the whole array, and split it into halves.

Before writing any code, let’s trace that on a concrete array:

              ┌───┬───┬───┬───┬───┬───┬───┬───┐
              │ 5 │ 3 │ 8 │ 6 │ 2 │ 7 │ 1 │ 4 │
              └───┴───┴───┴───┴───┴───┴───┴───┘

Splitting on the way down

To sort an array, cut it in half, sort each half, and merge the two sorted halves. “Sort each half” is the recursive step. We sort a half the same way, by cutting it in half, and so on.

We start with the whole array and cut it into two halves:

      ┌───┬───┬───┬───┐               ┌───┬───┬───┬───┐
      │ 5 │ 3 │ 8 │ 6 │               │ 2 │ 7 │ 1 │ 4 │
      └───┴───┴───┴───┘               └───┴───┴───┴───┘

To sort each half, we cut it in half too:

  ┌───┬───┐       ┌───┬───┐       ┌───┬───┐       ┌───┬───┐
  │ 5 │ 3 │       │ 8 │ 6 │       │ 2 │ 7 │       │ 1 │ 4 │
  └───┴───┘       └───┴───┘       └───┴───┘       └───┴───┘

If we keep cutting, we eventually reach subarrays of a single element. And a single element is already sorted, so there is nothing left to do. That is our base case. The splitting stops there:

┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
│ 5 │   │ 3 │   │ 8 │   │ 6 │   │ 2 │   │ 7 │   │ 1 │   │ 4 │
└───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘

Notice that no sorting work happens on the way down. We are only dividing the array into smaller and smaller subarrays. This is the same pattern as countUp going all the way down to countUp(0) before printing anything.

Merging on the way up

The sorting work happens as we come back up. Once a call has its two halves sorted, it merges them. The single elements merge into sorted pairs:

  ┌───┬───┐       ┌───┬───┐       ┌───┬───┐       ┌───┬───┐
  │ 3 │ 5 │       │ 6 │ 8 │       │ 2 │ 7 │       │ 1 │ 4 │
  └───┴───┘       └───┴───┘       └───┴───┘       └───┴───┘

The pairs merge into sorted fours:

      ┌───┬───┬───┬───┐               ┌───┬───┬───┬───┐
      │ 3 │ 5 │ 6 │ 8 │               │ 1 │ 2 │ 4 │ 7 │
      └───┴───┴───┴───┘               └───┴───┴───┴───┘

And the final merge produces the whole sorted array:

              ┌───┬───┬───┬───┬───┬───┬───┬───┐
              │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │
              └───┴───┴───┴───┴───┴───┴───┴───┘

This is the work on the way up that we saw in countUp and sumTo. Here, that work is the merge.

The order the merges happen in

The diagrams above are drawn level by level, which makes it look like the whole bottom row merges first, then the next row, and so on. That is not how the recursion actually runs. Recursion goes depth-first: a call goes all the way down its left half, finishes that half completely, and only then starts on its right half.

So for our array, the merges actually happen in this order:

1. merge [5] and [3]        -> [3 5]
2. merge [8] and [6]        -> [6 8]
3. merge [3 5] and [6 8]    -> [3 5 6 8]      (left half now fully sorted)
4. merge [2] and [7]        -> [2 7]
5. merge [1] and [4]        -> [1 4]
6. merge [2 7] and [1 4]    -> [1 2 4 7]      (right half now fully sorted)
7. merge [3 5 6 8] and [1 2 4 7] -> [1 2 3 4 5 6 7 8]

This ordering is the difference between the top-down version and the bottom-up passes from before. On this array, both do the same set of merges. The bottom-up version does them level by level. The recursive version does them depth-first.