Problem: Insertion Sort with Binary Search

Let’s revisit insertion sort and try to make it do fewer comparisons.

Here is the shift-based insertion sort from the chapter:

public static void insertionSort(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    int key = arr[i];
    int j = i;
    while (j > 0 && arr[j - 1] > key) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = key;
  }
}

The inner loop does two jobs at once. It finds where the key belongs, by comparing the key with one element after another, and it opens a gap there, by shifting each larger element one slot to the right. The finding part is a linear search. It scans the sorted portion from right to left and stops at the first element that is not larger than the key.

The sorted portion is sorted, and we know a faster way to search a sorted array. So the idea is to split the inner loop into its two jobs, and then do the finding job with binary search.

The signatures of the methods in Java might look like this:

// Returns the index in arr[0..end-1] where key belongs, after any elements
// equal to key.
// Pre: arr[0..end-1] is sorted.
private static int insertionPosition(int[] arr, int key, int end) {
  // Your implementation goes here
}

// Moves arr[start..end-1] one slot to the right, overwriting arr[end].
private static void shiftRight(int[] arr, int start, int end) {
  // Your implementation goes here
}

public static void insertionSort(int[] arr) {
  // Your implementation goes here
}

insertionPosition answers the question “where does this key go?” for the sorted portion arr[0] through arr[end - 1]. shiftRight opens the gap. insertionSort calls the first, then the second, then writes the key into the gap.

Suppose the sorted portion is the first four elements and the key is the fifth:

┌───┬───┬───┬───┬───┐
│ 2 │ 5 │ 5 │ 8 │ 5 │
└───┴───┴───┴───┴───┘
  0   1   2   3   4
                  key

The key 5 belongs at index 3, after the two 5s that are already there. So insertionPosition(arr, 5, 4) should return 3. Then shiftRight(arr, 3, 4) moves the 8 from index 3 to index 4, and the sort writes the key into index 3:

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

The “after any elements equal to key” part of the contract is what keeps the sort stable. The chapter’s linear scan uses a strict >, so it stops as soon as it meets an element equal to the key, and the key is placed after that element. Your binary search has to make the same choice. If it returns the index before the equal elements instead, the sort will still sort, but it will no longer be stable.

Let’s think of some special or edge cases as well:

  • If the array is empty or has one element, there is nothing to shift and nothing to compare.
  • If the key is larger than everything in the sorted portion, its position is end, and shiftRight has nothing to move.
  • If the key is smaller than everything in the sorted portion, its position is 0, and every element in the sorted portion moves.
  • If every element in the array is the same, every key belongs at the end of the sorted portion, and nothing moves.