Bottom-Up Merge Sort

What we just did is called the merge sort. (More accurately, it is called the bottom-up merge sort, but we will get to that later.) We start from $n$ sorted subarrays of length $1$ and merge adjacent pairs in each pass until we have just one sorted subarray of length $n$.

Let’s write the code for the merge sort step by step, starting with the method signature:

private static void merge(int[] arr, int start, int mid, int end) {
  // Assume our implementation from an earlier section is here
}

public static void mergeSort(int[] arr) {
  // implementation goes here
}

I will start with a simplifying assumption: the length of the input array is a power of $2$ (i.e., $n=2^k$ for some integer $k$). This will make our implementation easier to understand, and we can handle the general case later.

The width of the subarrays we are merging doubles on each pass: $1,2,4,8,\dots$. So let’s start with an outer loop that iterates width from 1 up to (but not including) n, doubling it each time:

public static void mergeSort(int[] arr) {
  int n = arr.length;
  for (int width = 1; width < n; width *= 2) {
    // merge all adjacent pairs of subarrays of this width
  }
}

Each iteration of this loop is one pass over the array. Within a pass, we need to merge every adjacent pair of subarrays of length width. The first pair starts at index 0, the next pair starts at index 2 * width, the one after that at 4 * width, and so on. So let’s add an inner loop that iterates start across the array in steps of 2 * width:

public static void mergeSort(int[] arr) {
  int n = arr.length;
  for (int width = 1; width < n; width *= 2) {
    for (int start = 0; start < n; start += 2 * width) {
      // merge the pair of subarrays that begins at start
    }
  }
}

For each start, the left subarray runs from start to start + width - 1, and the right subarray runs from start + width to start + 2 * width - 1. That is exactly the input our merge method expects, with mid = start + width and end = start + 2 * width:

public static void mergeSort(int[] arr) {
  int n = arr.length;
  for (int width = 1; width < n; width *= 2) {
    for (int start = 0; start < n; start += 2 * width) {
      int mid = start + width;
      int end = start + 2 * width;
      merge(arr, start, mid, end);
    }
  }
}

Because merge writes its result back into arr, mergeSort sorts the input array directly rather than producing a new one.

Our power-of-$2$ assumption guarantees that 2 * width always divides n evenly. That means mid and end never run past the end of the array, so every call to merge gets two full subarrays of length width.