In the insertion sort algorithm, the outer loop iterates over the list using the index variable i. Here are some key facts about how the list content relates to i in the outer loop:
- The sub-list from 0 to i-1 is sorted after each iteration. The elements to the right of i are unsorted.
- i represents the delimiter between the sorted and unsorted parts of the list.
- On each iteration, the element at index i is 'inserted' into the correct position in the sorted sub-list from 0 to i-1.
- So as i increments, the sorted region grows by one element each time.
- When i reaches the end of the list, the entire list is sorted.
- The inner loop repeatedly swaps element i backwards until it is in sorted position within the sorted sub-list 0 to i-1.
So in summary, i represents the split between sorted and unsorted parts of the list, and increments by 1 each iteration to grow the sorted region from left to right. The inner loop positions element i correctly each time.