Get the first two items in sorted order. Then the first three. Then the first four, and so on.
Algorithm
1. Iteration #1: If the first two items are in relative order, you're done. Otherwise swap them.
2. Iteration #2: Consider the third item and the two items to its left. Insert the third item in its correct position so that the first 3 are in sorted order.
3. Continue this process until the last item is placed.
Exercise
In the table below, show what the data looks like after each iteration of the algorithm.
What is the Loop Invariant?
A "loop invariant" is a true statement you can make about the data at each step. It does not describe how the algorithm works.
Complete this sentence: "At the ith step of the algorithm ... "