Insertion Sort

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.

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 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$.