Merging Two Sorted Arrays

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

k=0: 1 from arr2      k=4: 7 from arr2
k=1: 2 from arr1      k=5: 8 from arr2
k=2: 5 from arr1      k=6: 9 from arr1 (arr2 is exhausted)
k=3: 6 from arr2

Merged array: [1, 2, 5, 6, 7, 8, 9].

Time $O(n+m)$: the loop fills one slot per iteration and there are $n+m$ slots, with constant work each. Auxiliary space $O(n+m)$, the merged array. There is no best or worst case in the asymptotic sense. The input values decide which branch runs on each iteration. That changes the constant factor, but it does not change how many iterations there are.

The merge is $O(n)$. It places each element once and never moves an element past another. Insertion sort on the combined array is $O(n^2)$ in the worst case. It does not use the fact that the two halves are already sorted, and it may move an element past many others.