Recursive Merge Sort

Assume this method exists. It sorts arr[start] through arr[end - 1], given that arr[start] through arr[mid - 1] and arr[mid] through arr[end - 1] are each sorted:

private static void merge(int[] arr, int start, int mid, int end)

Solution

Work before the call runs on the way down, as the calls go deeper. Work after the call runs on the way up, as the calls return. The merge is work after the calls: a range can only be merged once both of its halves have come back sorted.

Exercise

Write merge sort recursively, with a public method that takes only the array and a private helper that sorts a range:

public static void mergeSort(int[] arr) {
  // ...
}

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

Solution

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

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);
  mergeSort(arr, mid, end);
  merge(arr, start, mid, end);
}

Solution

1. [5] + [1]                  -> [1 5]
2. [8] + [4]                  -> [4 8]
3. [1 5] + [4 8]              -> [1 4 5 8]
4. [7] + [2]                  -> [2 7]
5. [6] + [3]                  -> [3 6]
6. [2 7] + [3 6]              -> [2 3 6 7]
7. [1 4 5 8] + [2 3 6 7]      -> [1 2 3 4 5 6 7 8]

The left half is fully sorted (merges 1 to 3) before any merge on the right half happens.

Solution

Time $O (n lo g n)$ : the merges at one level of the recursion tree cover the array once, $O (n)$ , and halving $n$ down to $1$ gives $lo g_{2} n$ levels. Auxiliary space $O (n)$ : the largest temporary array in merge has $n$ elements, and only one exists at a time. The call stack is the part the bottom-up version does not have. It is $O (lo g n)$ frames deep. The $O (n)$ term dominates it, so the auxiliary space is still $O (n)$ , the same as the bottom-up version.

Solution

For a range of length $2$ or more, the midpoint start + (end - start) / 2 is strictly between start and end, so the range splits into two nonempty halves that stay inside the array, and a range of length $0$ or $1$ stops the recursion. An odd-length range just gives halves that differ by one element.