In-Place Merge: Analysis

Here is the in-place merge method, with the loop condition from the previous section.

public static void merge(int[] arr, int mid) {
  for (int k = 0; k < mid && mid < arr.length; k++) {
    // if the current element is larger than the first element of the second
    // half, we need to move arr[mid] to arr[k], and shift everything from
    // arr[k] to arr[mid - 1] to the right
    if (arr[k] > arr[mid]) {
      int temp = arr[mid];
      for (int i = mid; i > k; i--) {
        arr[i] = arr[i - 1];
      }
      arr[k] = temp;
      mid++;  // the boundary between the two sorted halves moves right after each insertion
    }
  }
}

Start with the space, because saving space is why we tried this. We are not creating a new array to hold the merged result. The only extra space is the variables k, i, and temp, and that is a constant amount no matter how long the array is, so the auxiliary space is $O(1)$.

Now let’s switch to time complexity. Let $n$ be the length of the input array.

• The outer loop advances k by one each time and stops when k reaches mid, and mid is never more than $n$. So the outer loop runs $O(n)$ times.
• The inner loop shifts the elements at indices k through mid - 1, so it runs mid - k times. That is at most $n$, so the inner loop is $O(n)$.

Multiplying the two bounds gives $O(n^2)$ as an upper bound. Now, is there an input that actually costs that much?

Yes. Take the case where every element in the second half is smaller than every element in the first half. Then arr[k] > arr[mid] is true on every iteration, so every iteration enters the inner loop and shifts. Say each half has $n/2$ elements. Each insertion moves both k and mid right by one, so mid - k stays at $n/2$ and each of the $n/2$ insertions shifts $n/2$ elements. That is about $n^2/4$ moves in total, which is $O(n^2)$.

The best case is the opposite arrangement. Every element in the first half is smaller than every element in the second half. Then arr[k] > arr[mid] is false every time. We never enter the inner loop, and the outer loop just advances k across the first half. That is $O(n)$.

We can do even better in that case if we add one check. If arr[mid - 1] <= arr[mid], then the largest element of the first half is no larger than the smallest element of the second half, so the array is already merged and we can return right away. If we put that check at the top of the method, the best case becomes $O(1)$.

Now compare that with the merge that allocates a new array. That one runs in $O(n)$ time and $O(n)$ auxiliary space. The in-place merge runs in $O(1)$ auxiliary space, but its worst case is $O(n^2)$ time.

That is why this simple in-place merge is not commonly used. There are more advanced in-place merge algorithms that do better, but we will not cover them in this course.