Insertion Sort Algorithm with Complexity Analysis, Best Case and Worst Case Scenarios

Algorithms have always been part of our life, even before the invention of computing machines.
However, computers rely on algorithms for everything that they do.
Designing an algorithm is not a difficult task, but designing an efficient algorithm for a complex problem can be challenging at times.
As a software engineer, one is always thinking about making best use of space and time available to them.
In the world of computers, saving time means using less computing power and saving space means using less memory.
This video will explain a simple sorting algorithm called insertion sort.
Formal definition of the sorting problem is that our input is a sequence of numbers in random order, let us call them a1, a2, all the way to an.
Our output will be a reordering of these numbers such that a1’, a2’, all the way to an’ are in increasing order.
Insertion sort is similar to how a person arranges a set of playing cards in their hand while picking one card at a time from the pile of cards on the table.
They pick one card and find its appropriate place in their hand by comparing it with each card from right to left.
The cards in their hand are always properly sorted.
Once the pile of cards on the table is finished, the hand is properly sorted.
This will be an in-place sorting algorithm.
This means that it will use the same memory where the sequence of unsorted keys already resides.
Probably one spot, or variable, will be used to swap the key trying to find its place in the sorted subsequence.
Our algorithm will take an array of numbers, in this example, we will use 10 numbers, let us call them keys.
Our algorithm will be sorting this array of 10 keys in ascending order.
The algorithm divides the array in two parts.
Left part is always sorted.
Right part is not sorted.
Our loop will start from the second element of the array, the first element is the only element left in our left sorted subarray.
Since it is the only element, it is safe to say that this subarray with one element is sorted.
First element of the right unsorted subarray will be the key that will try to find its proper place in the left sorted subarray.
We will store it in a variable so that its place becomes available for moving other elements if necessary.
Our algorithm will compare it with the right most element of our left sorted subarray.
Since the key in question is smaller than the right most element in our sorted subarray, we will move it to the right one step.
There are no more elements to compare with, so the key will be placed in the empty spot in the left sorted subarray.
Now our left sorted subarray has two keys.
Next iteration of our algorithm will place the first element of the right unsorted subarray in our swap variable.
Our algorithm will compare it with the right most element of our left sorted subarray.
Since the key in question is smaller than the right most element in our sorted subarray, we will move it to the right one step.
Our algorithm will compare the key with the next element of our left sorted subarray.
Since the key in question is smaller than this element in our sorted subarray, we will place it in this empty spot.
Now our left sorted subarray has three keys.
We will keep on repeating this logic until our right unsorted subarray becomes empty.
That is how an insertion sort algorithm works.
We can analyze its complexity by calculating the cost of executing each line of this algorithm and identifying the number of times each time will be executed.
The overall complexity of this algorithm will be the sum of complexity of each line.
Complexity of each line will be calculated by the cost of executing the line multiplied by the number of times that line will be executed.
If we simplify this expression, we will get the complexity of this algorithm.
The best case scenario of insertion sort occurs when the input array is already sorted.
This would mean that our inner loop will be executed only once for each outer iteration.
That would simplify our complexity to an + b making it a linear function of n where n is the number of elements in the input array.
However, when calculating complexity, one should not expect the best case scenario to occur very frequently.
That is why calculating the worst case and average case complexities are more important.
In the worst case scenario, the input array would be sorted in descending order.
This would mean that our inner loop will be executed to compare the key with each element of the left sorted subarray resulting in maximum runtime complexity.
This would cause the complexity to become an2 + bn + c hence becoming a quadratic function of n.
Although insertion sort is a simple sorting algorithm which is good for sorting smaller sets, if the input array becomes large, the cost of using this algorithm would increase exponentially.
For problems involving millions of numbers, it would be better to use an algorithm with lesser complexity.