Insertion Sort

Overview

Property	Value
Best Case	$\Omega (n)$
Worst Case	$O(n^2)$
Avg. Case	$O(n^2)$
Aux. Memory	$O(1)$
Stable	Yes
Adaptive	Yes

void insertion_sort(const int n, int A[static n]) {
  for (int i = 1; i < n; ++i) {
	int key = A[i];
	int j = i - 1;
	for (; j >= 0 && A[j] > key; --j) {
	  A[j + 1] = A[j];
	}
	A[j + 1] = key;
  }
}

Loop Invariant

Consider loop invariant $P$ given by

A[0:i-1] consists of the original A[0:i-1] elements but in sorted order.

We prove $P$ maintains the requisite properties:

• Initialization
  • When i = 1, A[0:0] contains a single element. This trivially satisfies $P$.
• Maintenance
  • Suppose $P$ holds for some 1 ≤ i < n. Then A[0:i-1] consists of the original A[0:i-1] elements but in sorted order. On iteration i + 1, the nested for loop puts A[0:i] in sorted order. At the end of the iteration, i is incremented meaning A[0:i-1] still satisfies $P$.
• Termination
  • The loop ends because i < n is no longer true. Then i = n. Since $P$ holds, this means A[0:n-1], the entire array, is in sorted order.

Analogy

Suppose you have a shuffled deck of playing cards face-down on a table. Start by grabbing a card from the deck with your left hand. For the remainder of the cards, use your right hand to transition the topmost card to the end of your left hand. If the newly placed card isn’t in sorted order, move it one position closer to the start. Repeat until it’s in sorted order.

If you repeat this process for every card in the deck, your left hand will eventually contain the entire deck in sorted order.

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).