Insertion Sort: Comparisons and Swaps

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

Swaps

Every swap exchanges the key with the element just to its left, and only when that element is larger than the key. That is an adjacent, out-of-order pair, which is one inversion, and the swap removes it without changing the relative order of any other pair. So, as with bubble sort, insertion sort makes exactly one swap per inversion in the input.

That is the same swap count as bubble sort on every input.

Comparisons

The comparison is arr[j - 1] > arr[j], and the inner loop makes it once per iteration. Each iteration either swaps, when the comparison is true, or stops the loop, when it is false. So for each key, the comparisons are its swaps plus one more, the failed comparison that ends the loop. The one exception is a key that swaps all the way to index 0, where j > 0 stops the loop before any comparison fails.

Add that up over the whole sort. The comparisons are the total swaps, plus at most one per key. Since the first key never enters the loop, that is

$$\text{comparisons}\le \text{swaps}+(n-1)$$

Here are the counts for each case.

• An already-sorted array has $0$ inversions. Each key from the second one on makes one comparison, finds its left neighbor is not larger, and stays. That is $n-1$ comparisons and $0$ swaps, which is $O(n)$.
• A reverse-sorted array has $\frac{n(n-1)}{2}$ inversions. Every key swaps all the way to index 0, so every comparison is followed by a swap and no comparison ever fails. That is $\frac{n(n-1)}{2}$ comparisons and the same number of swaps.
• A random array has about $\frac{n(n-1)}{4}$ inversions. That gives about $\frac{n(n-1)}{4}$ swaps and about $\frac{n(n-1)}{4}+n$ comparisons. Halving does not change the growth rate, so this is still $O(n^2)$.

Nearly sorted input

Take an array that is sorted except for one element, and compare the two ways that can happen.

[5, 1, 2, 3, 4] has one large element at the front. It has $4$ inversions. Each of the keys 1, 2, 3, 4 swaps past the 5 once and stops. That is $4$ swaps and $7$ comparisons.

[2, 3, 4, 5, 1] has one small element at the end. It also has $4$ inversions. The keys 3, 4, 5 each make one comparison and stay. The key 1 swaps four times to the front. That is again $4$ swaps and $7$ comparisons.

The counts are the same in both arrays. The position of the out-of-place element does not change them. An array with few inversions is cheap to sort, wherever the inversions are.

Running time and space

In the worst case, reverse-sorted input, insertion sort is $O(n^2)$. In the best case, sorted input, it is $O(n)$. In general its cost is about $n$ plus the number of inversions.

The auxiliary space is $O(1)$: i, j, and temp.