Insertion Sort

Overview

Insertion sort iterates upward through an array, repeatedly putting each element into sorted order in the subarray preceding the cursor.

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

This sorting algorithm works analogously to a sorting method used with a deck of playing cards. 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.

Loop Invariant

Insertion sort has a 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.