Implementing the Merge Process

Let’s implement the merge process. Here is the method signature:

public static int[] merge(int[] arr1, int[] arr2) {
  // ...
}

Notice that we are returning a new array that contains the merged result. We will create a new array that has enough space to hold all the elements from both input arrays:

public static int[] merge(int[] arr1, int[] arr2) {
  int[] merged = new int[arr1.length + arr2.length];
  // ...
  return merged;
}

We need to go over every element in each array. But I like to think of the merge process differently: we go over every slot in the merged array and fill each one with the next smallest element from the input arrays. So we will have a loop that goes through the merged array:

public static int[] merge(int[] arr1, int[] arr2) {
  int[] merged = new int[arr1.length + arr2.length];
  for (int k = 0; k < merged.length; k++) {
    // ...
  }
  return merged;
}

We also need two pointers: i for the current index in arr1, and j for the current index in arr2. We will start both at 0:

public static int[] merge(int[] arr1, int[] arr2) {
  int[] merged = new int[arr1.length + arr2.length];
  int i = 0, j = 0;
  for (int k = 0; k < merged.length; k++) {
    // ...
  }
  return merged;
}

Now let’s fill in the body of the loop. We will compare the elements at i and j. We will put the smaller one in the merged array at index k, and then we will move the corresponding pointer (i or j) to the next index in its array:

public static int[] merge(int[] arr1, int[] arr2) {
  int[] merged = new int[arr1.length + arr2.length];
  int i = 0, j = 0;
  for (int k = 0; k < merged.length; k++) {
    if (arr1[i] <= arr2[j]) {
      merged[k] = arr1[i++];
    } else {
      merged[k] = arr2[j++];
    }
  }
  return merged;
}

This code has the problem we saw at the end of the trace in the previous section. If you run it on [1, 3, 5] and [2, 4, 6, 7], it places 1, 2, 3, 4, 5 and then it fails. At that point i is 3 and arr1 has no elements left, but the loop still has two slots to fill. So it evaluates arr1[i], which is arr1[3], and Java throws an ArrayIndexOutOfBoundsException.

We can handle that by checking whether i or j has moved past the last index of its array. Those two checks have to come first, before the comparison, because the comparison reads arr1[i] and arr2[j] and is only safe once we know both indices are still in range:

public static int[] merge(int[] arr1, int[] arr2) {
  int[] merged = new int[arr1.length + arr2.length];
  int i = 0, j = 0;
  for (int k = 0; k < merged.length; k++) {
    if (i >= arr1.length) {
      merged[k] = arr2[j++];
    } else if (j >= arr2.length) {
      merged[k] = arr1[i++];
    } else if (arr1[i] <= arr2[j]) {
      merged[k] = arr1[i++];
    } else {
      merged[k] = arr2[j++];
    }
  }
  return merged;
}