Implementing Insertion Sort

Let’s implement insertion sort. Here is the method signature:

public static void insertionSort(int[] arr) {
  // ...
}

We need to go over every element in the array, so we will need a loop that goes through the array.

public static void insertionSort(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    // ...
  }
}

For each element, we need to insert it into the correct position in the sorted portion of the array that comes before it.

• When we are at index i, the portion of the array that comes before it is arr[0] to arr[i-1].
• We want that portion to be sorted. So we will maintain the invariant that arr[0] to arr[i-1] is always sorted at the start of each iteration of the loop.
• We will call the element at index i the “key”.
• We will move the key into its correct position by swapping it with the element to its left, again and again, as long as that element is larger than the key.

We will need another loop that starts the key at index i and moves it backwards toward 0. We keep track of the key’s current position with an index j. As long as the element to the left of the key (arr[j - 1]) is larger than the key (arr[j]), we swap them and move j one step to the left. Here is the code:

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

The loop invariant

The invariant of the outer loop is that arr[0] to arr[i-1] is sorted at the start of each iteration. Each iteration inserts the key at index i into that portion, so the sorted portion is one element longer at the start of the next iteration. The outer loop ends when i reaches arr.length, and the invariant then says arr[0] to arr[arr.length - 1] is sorted, which is the whole array.