5/1/201536 Termination InsertionSort(A, n) { for j = 2 to n { key = A[j]; i = j - 1; ▷ Insert A[j] into the sorted sequence A[1..j-1] while (i > 0) and (A[i] > key) { A[i+1] = A[i]; i = i – 1; } A[i+1] = key } } 1 j=n+1 Sorted Upon termination, A[1..n] contains all the original elements of A in sorted order.
{}