Insertion Sort’s Anatomy
An interesting analogy that helps ingrain the sorting concept in your memory
As a Software Engineer or a fresh Computer Science graduate, I have always had problems with “properly” understanding the Insertion Sort algorithm. Well, at least at first, not anymore. If you read this and have a grin on your face, chances are you also went or are going through the same issue.
Not anymore my friend.
To crack the coding interviews of tech companies, people prepare Data Structures and Algorithms (DSA) in depth. This bodes well unless you have taken a gap from practicing coding problems and you have to go back to the preparation phase for a company switch or something. More often than not people try to refresh their basic knowledge on DSA first and the first topic is mostly “sorting”. In that, the first and most basic sorting algorithm that comes is the “Insertion Sort”.
Let’s “properly” understand this algorithm once and for all and be done with it.
A card game: The Analogy
Everyone has played at least one card game in their lives. In most of the card games each of the players get a hand of playing cards. Now it is a natural instinct of a card player to have the hand of cards always sorted, irrespective of the motive of the game.
Let’s look closer on how does a player go about sorting a hand of cards.
Consider the set of cards are stacked face down.
The player pulls the a card with his/her right hand, comprehends the value of the card and puts it on the appropriate position on his/her left hand. Thus, keeping the left hand of cards always sorted.
Insertion Sort
Analogizing with the above game:
Given an input in the form of an n-element array, the insertion sort algorithm requires us to maintain the array in 2 logical parts: sorted part (left hand) and unsorted part (right hand). We need to take elements from the unsorted part and put it into the appropriate position in the sorted part such that when the algorithm is done executing, the length of the sorted part must be equal to n and the length of the unsorted part must be equal to 0.
The algorithm (pseudo code):
Done, right?
It is that simple.
First, we defined sorted and unsorted parts of the array by taking the first element, A[0], as sorted (as a single number is inherently sorted) and rest of the array as unsorted.
Then, we are making sure that the sorted part is intact and growing with each iteration the for loop (lines 1–8).
Some more details
In the world of mathematics, the insertion sort algorithm can be proved using a technique called mathematical induction. Basically, let’s see how can we prove that the above algorithm, in fact, outputs the array in a sorted manner for any given input array.
Mathematical induction works by taking a base property from the algorithm which is true for all the stages of the algorithm throughout its execution. This property is called an invariant. In our case, since the algorithm executes in a loop, this property will be called a loop invariant.
Once the loop invariant is determined, we need to satisfy 3 conditions:
- Initialization: This condition implies that the loop invariant holds true even before the very first iteration of the loop.
- Maintenance: This condition implies that the loop invariant property is maintained with each iteration of the loop.
- Termination: This condition implies that when the loop terminates the loop invariant gives us a useful property that shows the correctness of the algorithm.
Loop Invariant of Insertion Sort
The property that never changes is that the left part (the sorted part) always remains sorted.
Hence, the loop invariant for us is the left part of the array being always sorted.
Initialization
The loop starts from the 2nd element, which means even before the first loop iteration we have the left part already sorted, since there is only one element.
Maintenance
After each iteration “i”, the array A[0 to i-1] (left subarray) always remains sorted.
Termination
After the last iteration “i”, i is equal to n. Since we have the array A[0 to i-1] always sorted, we can say that after this last iteration the subarray A[0 to n-1] is in fact the entire array and is sorted.
Hence the algorithm is correct.
Conclusion
Insertion sort always maintains the left part of the input array sorted and grows it to match the length of the original array.
Please like, share and follow for more such articles.
