The Common Way to Merge

If you look up merge in a textbook or online, you will often see a version whose signature looks like an in-place merge. It is not. It uses an auxiliary array to hold the merged result.

The merge itself receives:

• one array as the input, with two indices start and end that mark the subarray from index start to end - 1
• an index mid such that the elements from index start to mid - 1 are sorted, and the elements from index mid to end - 1 are also sorted

The goal is to merge these two subarrays so that, when the method is done, the elements from index start to end - 1 are sorted. This is usually done with a new array. The new array has enough space to hold all the elements from start to end - 1. The method fills it with the elements from the input array in sorted order, and then copies the merged result back to the input array.

Here is the code for it:

private static void merge(int[] arr, int start, int mid, int end) {
  int[] merged = new int[end - start];

  int i = start, j = mid;
  for (int k = 0; k < merged.length; k++) {
    if (i >= mid) {
      merged[k] = arr[j++];
    } else if (j >= end) {
      merged[k] = arr[i++];
    } else if (arr[i] <= arr[j]) {
      merged[k] = arr[i++];
    } else {
      merged[k] = arr[j++];
    }
  }

  for (int k = 0; k < merged.length; k++) {
    arr[start + k] = merged[k];
  }
}

The first loop is the loop from our first merge, with arr[start] through arr[mid - 1] in place of arr1 and arr[mid] through arr[end - 1] in place of arr2. The second loop copies the merged result back into arr.

Let $n$ be the number of elements from start to end - 1. Each loop runs $n$ times, so the method runs in $O(n)$ time. The auxiliary array has $n$ slots, so the method uses $O(n)$ auxiliary space. But the method takes one array and returns nothing, so it looks like it works in place.

We now have a merge that joins two sorted subarrays into one. Our job is to sort an array that is not sorted at all, and the merge only works when the two subarrays it is given are already sorted. So where would two sorted subarrays come from?