In-Place Merge

Let’s think about what an in-place merge might look like. Assume we are given one array as the input, and there is an index mid such that the elements from index 0 to mid - 1 are sorted, and the elements from index mid to the end of the array are also sorted. We want to merge these two sorted subarrays in place.

Here is the signature of the method we want to implement:

public static void merge(int[] arr, int mid) {
  // implementation goes here
}

We still need to go over every element of the array, so let’s place a loop that goes from 0 to arr.length - 1:

public static void merge(int[] arr, int mid) {
  for (int k = 0; k < arr.length; k++) {
    // implementation goes here
  }
}

Now think about what happens at a given k. The element arr[k] is the smallest one left in the first half, and arr[mid] is the smallest one left in the second half. So the element that belongs at position k is whichever of those two is smaller.

• If arr[k] is not greater than arr[mid], then it already belongs at position k. We can just move on to the next k.
• If arr[k] is greater than arr[mid], then arr[mid] belongs at position k. We need to move arr[mid] there, and to make room we need to shift everything from index k to mid - 1 one position to the right.

Here is what that looks like:

Before:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  2  │  3  │  5  │  1  │  4  │  6  │  7  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
    k=0                ↑
                      mid

After:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  1  │ ░2░ │ ░3░ │ ░5░ │  4  │  6  │  7  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
          k=1                ↑
                            mid

Look at what happened to mid in that diagram. It moved right by one. The value 1 moved from the second half into the first half, and 2, 3, and 5 each moved one position to the right to make room for it. So the first half grew by one element and the second half shrank by one. If we did not move mid, it would no longer point at the first element of the second half, and the next comparison would read an element of the first half instead.

If we continue the process, values 2 and 3 stay where they are because they are smaller than 4. But when we get to 5, we need to move 4 into position k, shifting 5 (and anything else from index k to mid - 1) one position to the right to make room for it.

Before:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  1  │  2  │  3  │  5  │  4  │  6  │  7  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
                      k=3    ↑
                            mid

After:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  1  │  2  │  3  │  4  │ ░5░ │  6  │  7  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
                            k=4    ↑
                                  mid

If we continue this process, we will end up with a fully merged array.

We still need to decide when the loop stops. The loop we sketched runs k to the end of the array, but that is more than we need. There are two ways the merge can finish early.

The first is that k reaches mid. Everything from k onward is then the part of the second half that we never moved. That part was already sorted, so there is nothing left to do.

The second is that mid reaches the end of the array. That means the second half is empty. Every element of it has already been moved into place, so again there is nothing left to do.

So the loop should keep going only while k < mid and mid < arr.length.