insertion sort is an algorithm that solves the sorting problem. constituents a sequence of n numbers \{a_1, \dots a_{n}\}, called keys intuition Say you have a sorted list; sticking a new element into the list doesn’t change the fact that the list is sorted. requirements Insertion sort provides an ordered sequence \{a_1’, \dots a_{n}’\} s.t. a_1’ \leq \dots \leq a_{n}’ void insertion_sort(int length, int *A) { for (int j=1; j<length; j++) { int key = A[j]; // insert the key correctly into the // sorted sequence, when appropriate int i = j-1; while (i > 0 && A[i] > key) { // if things before had // larger key // move them A[i+1] = A[i]; // move it down // move our current value down i -= 1; } // put our new element into the correct palace A[i+1] = key; } } This is an O\left(n^{2}\right) algorithm. additional information proof After iteration i of the outer loop, A[:i+1] is sorted. Base case: after iteration 0, the list A[:1] (i.e. list of one element) is sorted. For any 0 < k < n, the inductive hypothesis holds for i=k-1, then it holds for i=k because we are sticking the list into before the smallest element bigger than the main element. The inductive hypothesis holds or all i = 0 \ldots n-1, that would tell us via the inductive hypothesis the list A[:n] is sorted. proof We use loop invariant method to show that our algorithm is correct. Our invariant is that the array A[0, \dots, j-1] is sorted \forall j 0 \dots L+1. Initialization: at the first step, j=1 (second element), the subarray of A[0, \dots j-1] (namely, only the first element), is sorted trivially Maintenance: during each loop, we move j to the right, only being done when the subarray to the left is correctly sorted because of j is moving forward until length, it will terminate As j, by the end, covers the entire loop, our loop terminates at L+1 and invariant (sortedness) is maintained between A[0, \dots j].