Merge Sort, Recursively

We traced how merge sort splits the array down to single elements and merges the pieces back up. Now let’s write the code.

Sorting a range

Each recursive call in our trace sorts a piece of the array, not the whole array. So the recursive method needs to know which piece. It works on a range, from start to end - 1. We will write that as a helper, and give the public method the same simple signature as our earlier versions so it stays a drop-in replacement:

public static void mergeSort(int[] arr) {
  mergeSort(arr, 0, arr.length);
}

private static void mergeSort(int[] arr, int start, int end) {
  // ...
}

We have seen this pattern before: a public method that calls a private helper on the full range. We did the same thing when we wrote binary search recursively.

The base case

When does the recursion stop? When the range is so small that it is already sorted, which is a range of length 0 or 1. The length of the range is end - start, so:

private static void mergeSort(int[] arr, int start, int end) {
  if (end - start <= 1) {
    return;
  }
  // ...
}

The recursive case

If the range has more than one element, find the midpoint, sort each half, and merge the two sorted halves.

private static void mergeSort(int[] arr, int start, int end) {
  if (end - start <= 1) {
    return;
  }
  int mid = start + (end - start) / 2;
  mergeSort(arr, start, mid);  // sort the left half
  mergeSort(arr, mid, end);  // sort the right half
  merge(arr, start, mid, end);  // merge the two sorted halves
}

Let’s read it line by line:

• mid = start + (end - start) / 2 is the midpoint of the range, which is start plus half the range’s length. This is the same overflow-safe form we used for binary search.
• The two mergeSort calls are the recursive calls, and they happen on the way down.
• merge(arr, start, mid, end) runs only after both halves come back sorted. It is the work on the way up. It calls the merge we already wrote, with no changes to it.

Notice we do not need Math.min to keep mid and end from going past the end of an array whose length is not a power of 2. The midpoint always falls inside the range, so it splits the range into two shorter halves that both stay inside the array, and the recursion stops as soon as a range has at most one element.