.gif)
Insertion sort is the first algorithm introduced in the book, and it solves the basic sorting problem: given a list of numbers, it rearranges them so they appear in increasing order. These numbers are called keys. Often, each key is part of a larger record that includes extra information (called satellite data), like a student’s grades or age in a spreadsheet. When sorting by a key, the whole record moves with it, not just the number.
Insertion sort works like sorting playing cards in your hand. You start with an empty hand and take one card at a time from the pile. For each new card, you compare it with the cards already in your hand (from right to left) until you find the correct position to insert it. The cards in your hand always remain sorted, and each new card is inserted in its proper place.
INSERTION_SORT(A, n)
for i = 2 to n
key = A[i]
// insert A[i] into the sorted subarray A[1:i-1]
j = i - 1
while j > 0 and A[j] > key
A[j+1] = A[j]
j = j - 1
A[j+1] = key
A loop invariant is a property that stays true throughout the execution of a loop. It’s a tool for proving that an algorithm works correctly.
To use a loop invariant, you must show three things:
The invariant is true before the first iteration of the loop. That means the property already holds at the very start.
If the invariant is true before an iteration, it stays true after that iteration as well. So, the loop’s body doesn’t break the invariant — it preserves it every time.
When the loop finishes, the invariant (together with the reason the loop stopped) gives you a final property that proves the algorithm’s correctness.
Proving a loop invariant is like mathematical induction: