[leereeves]

That is the correct inductive step all by itself.

That's all we need to know: during each iteration after the first, the algorithm inserts the ith element into the previously sorted list from A[1] to A[i-1], giving a new sorted list from A[1] to A[i], and doesn't touch the rest because A[i] contains the maximum element.

Then when i=n the whole list is sorted.