Before we learn about Insertion Sort, Let's first See What an Algorithm means?

An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

In short, An algorithm is a sequence of steps that you use to solve a problem and get the desired output.

Sorting Algorithms are basic algorithms that everyone should know. These are the algorithms that we use in our daily life without even knowing.

Let's Take an example of a person playing cards:

In this video, we can see how while playing cards, we perform Insertion Sort without even knowing it. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left.

Insertion Sort Algorithm Steps and How it works:

Steps:

• If it is the first element, it is already sorted.

• Pick the next element.

• Compare with all the elements in sorted sub-list.

• Shift all the elements in a sorted sub-list that are greater than the value to be sorted.

• Insert the value.

• Repeat until the list is sorted.

Let us now understand How Insertion Sort works? :

Consider the following array A: 25, 17, 31, 13, 2

First Iteration: We Compare 25 with 17. The comparison shows 17< 25. Hence we swap 17 and 25.

The array now looks like this:

17, 25, 31, 13, 2

Second Iteration: Begin with the second element (25), but it was already swapped on for the correct position, so we move ahead to the next element.

Now hold on to the third element (31) and compare it with the ones preceding it.

Since 31 > 25, no swapping takes place.

Also, 31 > 17, no swapping takes place and 31 remains at its position.

The array after the Second iteration looks like this:

17, 25, 31, 13, 2

Third Iteration: Start the following Iteration with the fourth element (13), and compare it with its preceding elements.

Since 13 < 31, we swap the two.

Array now becomes: 7, 25, 13, 31, 2.

But there still exist elements that we haven’t yet compared with 13. Now the comparison takes place between 25 and 13. Since, 13 < 25, we swap the two.

The array becomes 17, 13, 25, 31, 2.

The last comparison for the iteration is now between 17 and 13. Since 13 < 17, we swap the two.

The array now becomes 13, 17, 25, 31, 2.

Fourth Iteration: The last iteration calls for the comparison of the last element (2), with all the preceding elements and makes the appropriate swapping between elements.

Since, 2 < 31. Swap 2 and 31.

Array now becomes: 13, 17, 25, 2, 31.

Compare 2 with 25, 17, 13.

Since, 2 < 25. Swap 25 and 2.

13, 17, 2, 25, 31.

Compare 2 with 17 and 13.

Since, 2 < 17. Swap 2 and 17.

Array now becomes:

13, 2, 17, 25, 31.

The last comparison for the Iteration is to compare 2 with 13.

Since 2 < 13. Swap 2 and 13.

The array now becomes:

2, 13, 17, 25, 31.

This is the final array after all the corresponding iterations and swapping of elements.

If we analyze, the algorithm sorts the input numbers in place which means, it rearranges numbers within the array A, with at most a constant number of them stored outside the array at any time. The input array A contains the sorted output sequence when the Insertion Sort algorithm procedure is finished.

Pseudocode:

INSERTION-SORT(A)
   for i = 1 to n
       key ← A [i]
        j ← i – 1
       while j > = 0 and A[j] > key
           A[j+1] ← A[j]
           j ← j – 1
       End while 
       A[j+1] ← key
  End for

Implementation in C++:

#include <iostream>
using namespace std;
void insertion_sort(int a[],int n){
    for (int i = 0; i < n - 1; i++){
        int e = a[i];
        //place the correct element at 'right' position in the sorted part
        int j = i-1;
        while(j >= 0 and a[j] > e){
            a[j+1] = a[j];
            j = j-1;
        }
        a[j+1] = e;
    }

}
int main() {
    int n, key;
    cin >> n;
    int a[1000];
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    insertion_sort(a, n);
    for(int i = 0; i < n; i++){
        cout << a[i] << " ";
    }
    return 0;
}

Time Complexity Analysis of Insertion Sort:

Even though insertion sort is efficient, still, if we provide an already sorted array to the insertion sort algorithm, it will still execute the outer for loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n.

Wherein for an unsorted array, it takes for an element to compare with all the other elements which means every n element compared with all other n elements. Thus, making it for n x n, i.e., n2 comparisons. One can also take a look at other sorting algorithms such as Merge sort, QuickSort, Selection Sort,, etc., and understand their complexities.

Worst Case Time Complexity [ Big-O ]: O(n^2)

Best Case Time Complexity [Big-omega]: O(n)

Average Time Complexity [Big-theta]: O(n^2)

Space Complexity: O(1) ( Since it is an in-place algorithm, it does not require extra space)

Is Insertion Sort Stable?

Yes!

( What does Unstable (Not Stable) mean in an algorithmic analysis? Where two elements are equal then their relative ordering should remain unchanged)

You can Practice questions of Insertion sort on GeeksforGeeks , Hacker Rank , Hacker Earth etc.

Thank You, I hope I was able to give a better understanding of Insertion Sort.