In the loop invariant here is the following: the list is split, into a prefix or a first part, and a suffix, the prefix is sorted, the suffix is not, and basically, the loop starts off with the prefix being nothing and it keeps increasing the size of the prefix by 1 until it gets through the entire list, at which point there's nothing in the suffix and entire prefix is sorted. 