Insertion Sort

Keep a sorted portion at the front of the array. Take the next element, the key, and move it left past every element larger than it, so the sorted portion grows by one. Repeat until the sorted portion is the whole array.

public static void insertionSort(int[] arr) {
  for (int i = 1; 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--;
    }
  }
}

At the start of the iteration with index i, arr[0] through arr[i - 1] is sorted. Each iteration inserts arr[i] into that portion, so the invariant holds for i + 1. The loop ends when i is arr.length, and the invariant then says arr[0] through arr[arr.length - 1], the whole array, is sorted.

start:       6 3 8 1 5
key 3:       3 6 8 1 5
key 8:       3 6 8 1 5
key 1:       1 3 6 8 5
key 5:       1 3 5 6 8

The swaps are the number of inversions in the input, one per adjacent out-of-order pair fixed. The comparisons are the swaps plus at most one failed comparison per key. Sorted: $0$ swaps, $n-1$ comparisons. Reverse sorted: $\frac{n(n-1)}{2}$ swaps and $\frac{n(n-1)}{2}$ comparisons, since every key travels to index 0 and no comparison fails. Random: about $\frac{n(n-1)}{4}$ swaps and about $\frac{n(n-1)}{4}+n$ comparisons.

$4$ swaps and $7$ comparisons on both. On the first, each of the keys 1, 2, 3, 4 swaps past the 5 once and stops. On the second, the keys 3, 4, 5 each make one comparison and stay, and the key 1 swaps four times to the front. Insertion sort’s cost tracks the number of inversions, not where they are.

public static void insertionSort(int[] arr) {
  for (int i = 1; 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;
  }
}

A swap is three assignments per element passed; a shift is one, plus one final write of the key. The time complexity is unchanged, $O(n^2)$ in the worst case. The key still moves past the same number of elements; only the constant factor per move changed.