Insertion Sort: Shifting Instead of Swapping

Here is the implementation of insertion sort again:

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--;
    }
  }
}

Let’s focus on the inner loop for a moment. Do we really need to swap the key with the element to its left every time?

Look at what a swap is doing here. It writes the larger element into the key’s position, and it writes the key back into the position the larger element came from. Then on the next step we read the key out of that position again and write it into the position to its left. So the key is copied over and over as it moves left, and every copy but the last one gets overwritten.

We could instead hold the key in a variable. Then each step only has to move one larger element to the right, and we write the key into the array once, at the end, when we have found its correct position.

Here is how that would look in code:

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;
  }
}

Let’s count the assignments. A swap is three assignments: into temp, into arr[j], and into arr[j - 1]. Moving one element to the right is one assignment. So if the key has to move past i elements, the swapping version does $3 i$ assignments and this version does $i + 2$ : one to save the key, one per element moved, and one to place the key. That is roughly a third of the assignments.

None of that changes the time complexity. Both versions are still $O (n^{2})$ in the worst case, because the key still has to move past every element larger than it. Big-Oh ignores constant factors, and a factor of three is a constant factor. The second version still does fewer assignments, and on a large array that makes the sort run faster.

The outer loop could start at 1 instead of 0. When i is 0 there is no element to the left of the key, so j starts at 0, the inner loop’s condition j > 0 fails immediately, and the assignment arr[j] = key writes arr[0] back onto itself. That whole iteration does nothing, so we could skip it by starting at 1.