Solution: Fewer Comparisons, the Same Shifts

Let’s do the split first, with the linear search still in place, so we can see the two jobs separately:

private static int insertionPosition(int[] arr, int key, int end) {
  int j = end;
  while (j > 0 && arr[j - 1] > key) {
    j--;
  }
  return j;
}

private static void shiftRight(int[] arr, int start, int end) {
  for (int k = end; k > start; k--) {
    arr[k] = arr[k - 1];
  }
}

public static void insertionSort(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    int key = arr[i];
    int j = insertionPosition(arr, key, i);
    shiftRight(arr, j, i);
    arr[j] = key;
  }
}

insertionPosition scans left from end the way the old inner loop did, but it only moves the index. shiftRight then opens a gap at that position by moving the elements from there to end - 1 one slot to the right. It works from the right end so that no element is overwritten before it has been copied. Then we write the key into the gap.

Now replace the linear search. The portion arr[0] through arr[end - 1] is sorted, so binary search applies. We keep a window low to high, look at its middle element, and discard the half that cannot hold the insertion point.

private static int insertionPosition(int[] arr, int key, int end) {
  int low = 0;
  int high = end - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] <= key) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return low;
}

The comparison is arr[mid] <= key, not <. When the element at mid equals the key, low moves past it, so the search keeps going to the right of any equal elements and returns the index after them. That is where the linear scan’s strict > stopped too, so the sort stays stable.

Let’s trace one call. The sorted portion is [2, 5, 5, 8], so end is 4, and the key is 5. We start with low at index 0 and high at index 3:

┌───┬───┬───┬───┐
│ 2 │ 5 │ 5 │ 8 │
└───┴───┴───┴───┘
  ↑           ↑
  L           H

The midpoint is index 1, whose value is 5. It is <= the key, so the key belongs to the right of it, and low moves to 2:

┌───┬───┬───┬───┐
│░2░│░5░│ 5 │ 8 │
└───┴───┴───┴───┘
          ↑   ↑
          L   H

The shaded cells are outside the window. The midpoint is now index 2, again a 5, again <= the key, so low moves to 3:

┌───┬───┬───┬───┐
│░2░│░5░│░5░│ 8 │
└───┴───┴───┴───┘
              ↑
             L,H

The midpoint is index 3, whose value is 8. That is greater than the key, so high moves to 2. Now low is 3 and high is 2, the loop stops, and we return low, which is 3. That is the slot right after the two 5s, as the contract requires.

Back in insertionSort, with i = 4, we call shiftRight(arr, 3, 4). The loop runs once, with k = 4, and copies arr[3] into arr[4]. Then we write the key into arr[3]:

┌───┬───┬───┬───┬───┐
│ 2 │ 5 │ 5 │ 5 │ 8 │
└───┴───┴───┴───┴───┘

Every step of the binary search compares the key with one element and then halves the window. For the key at index $i$ the window has $i$ elements, so insertionPosition makes about $lo g_{2} i$ comparisons. Summed over every key, that is at most about $n lo g_{2} n$ . The chapter’s version makes up to $\frac{n ( n - 1 )}{2}$ comparisons. So the comparisons drop from $O (n^{2})$ to $O (n lo g n)$ . On a random array that is a saving. But if the input array is already sorted, the binary search still makes $O (n lo g n)$ comparisons. The linear search makes one comparison per key on that input, $n - 1$ in total.

The shifts do not change. shiftRight moves every element between the insertion point and i - 1, and those moves are the rest of the work. If the key belongs at the front of a sorted portion of $i$ elements, all $i$ of them move. On a reverse-sorted array every key belongs at the front, so the shifts are $0 + 1 + \dots + (n - 1) = \frac{n ( n - 1 )}{2}$ . On a sorted array there are none.

So the refinement traded the linear best case for fewer comparisons everywhere else. Whether that is a good trade depends on the input you expect. If it is usually close to sorted, the chapter’s version is the better one.