Merge Sort for Any Length

So far we have assumed that the length of the array is a power of $2$. That assumption guarantees that every pass divides the array into pairs of equal-length subarrays, with nothing left over. Let’s drop it now and make merge sort work for any $n$.

Here is the code we ended up with:

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);
    }
  }
}

What goes wrong

Let’s trace this code on an array of length $7$, the same one we traced by hand earlier:

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  6  │  5  │  2  │  0  │  9  │  1  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘

In the first pass, width = 1, the inner loop sets start to 0, 2, 4, 6. The first three are fine: they merge (6, 5), (2, 0), and (9, 1). But when start = 6, we compute mid = 7 and end = 8, and call merge(arr, 6, 7, 8). The element at index 6 has no partner to its right. But the code still tries to merge it with a subarray that runs to index 7, and index 7 is past the end of a $7$-element array. That is an out-of-bounds access, and the program crashes.

There are two ways the pair that begins at start can fail to be a full pair:

• The right half is shorter than the left half. The pair has a full left half of width elements, but its right half runs past the end of the array. Here end is greater than n.
• There is no right half at all. The left half is a leftover subarray with no partner. Here even mid reaches or passes n.

Both have the same cause. We compute mid and end as if there were always 2 * width elements left after start. Near the end of the array there are not that many left.

The fix

We clamp mid and end to n, so neither one can go past the end of the array:

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 = Math.min(start + width, n);
      int end = Math.min(start + 2 * width, n);
      merge(arr, start, mid, end);
    }
  }
}

That is the only change from the power-of-$2$ version: two Math.min calls. Let’s check that it handles both boundary cases.

When the right half is shorter than the left half, end becomes n, and we call merge with a left half of length width and a shorter right half. Our merge method already handles halves of unequal length. It checks whether one half has run out before the other, and that is exactly what happens here. So this case needs nothing else.

When there is no right half, start + width is already at or past n, so mid becomes n and end becomes n too. The call is merge(arr, start, n, n): a left half of arr[start..n-1] and an empty right half. Merging a subarray with an empty subarray copies the non-empty one back unchanged.