# Insertion Sort ```python for i = 2 to n key = A[i] j = i - 1 while j > 0 and A[j] > key A[j + 1] = A[j] j = j - 1 A[j + 1] = key ``` - Sorting a deck of cards with hand. > [!important] Loop Invariant At the start of each iteration of the `for` loop, > the subarray `A[1:i - 1]` consists of the elements originally in `A[1:i - 1]`, > but in sorted order. - Best case: already sorted, $\Theta(n)$ - Worst case: reversely sorted, $\Theta(n^2)$ - [[asymptotic-notation|Asymptotic]] proof - Loops within loop, $O(n^2)$ - Assume the $n/3$ largest values occupy the first $n/3$ positions, each of them needs to be moved across $n/3$ positions in the middle, hence $(n/3)(n/3) = n^2/9$.