Bottom-Up 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, and it handles halves of unequal length and an empty right half:

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

Solution

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

Solution

start:              8 3 6 1 9 2 4
after width = 1:    3 8 1 6 2 9 4
after width = 2:    1 3 6 8 2 4 9
after width = 4:    1 2 3 4 6 8 9

In the first pass [4] is a one-element subarray with an empty right half, so merge copies it back unchanged. In the second pass [2, 9] merges with the one-element subarray [4].

Solution

Any length that is not a power of two, for example $7$ . In the first pass, start = 6 gives mid = 7 and end = 8, so merge reads past the end of the array and throws an ArrayIndexOutOfBoundsException.

Solution

The $n$ is the work per pass. The merges in one pass cover the array without overlapping, so each element is placed once per pass, $O (n)$ in total. The $lo g n$ is the number of passes: width doubles from $1$ until it is at least $n$ , which takes $lo g_{2} n$ doublings.

Solution

No. The number of passes depends only on $n$ , and each merge fills every slot of its range no matter what the values are. The values only decide which half the next element comes from. So the running time is $O (n lo g n)$ on every input, and the best case and the worst case are the same.