In-Place Merge and the Common Merge

One int array holds two sorted halves: arr[0] through arr[mid - 1] is sorted, and arr[mid] through arr[arr.length - 1] is sorted.

Solution

Start k at 0 and move it through the first half. If arr[k] is greater than arr[mid], then arr[mid] belongs at position k: shift arr[k] through arr[mid - 1] one position to the right, put the old arr[mid] at position k, and move both k and mid right by one. Otherwise arr[k] is already in its final position; move k right by one. Stop when k reaches mid or mid reaches arr.length.

Solution

Auxiliary space $O (1)$ . Worst-case time $O (n^{2})$ : when every element of the second half is smaller than every element of the first half, each of the $n /2$ insertions shifts $n /2$ elements.

Exercise

Write the merge that merge sort uses. It merges arr[start] through arr[mid - 1] with arr[mid] through arr[end - 1], given that each is sorted, so that arr[start] through arr[end - 1] is sorted:

private static void merge(int[] arr, int start, int mid, int end) {
  // ...
}

Solution

private static void merge(int[] arr, int start, int mid, int end) {
  int[] merged = new int[end - start];
  int i = start, j = mid;
  for (int k = 0; k < merged.length; k++) {
    if (i >= mid) {
      merged[k] = arr[j++];
    } else if (j >= end) {
      merged[k] = arr[i++];
    } else if (arr[i] <= arr[j]) {
      merged[k] = arr[i++];
    } else {
      merged[k] = arr[j++];
    }
  }
  for (int k = 0; k < merged.length; k++) {
    arr[start + k] = merged[k];
  }
}

Solution

Time $O (n)$ : each of the two loops runs $n$ times, one to fill merged and one to copy it back into arr. Auxiliary space $O (n)$ , the merged array.