Insertion Sort – A Stable Sorting Algorithm

Have you ever played card? If yes, then you’ll feel that insertion sort is somewhat similar to arranging cards in your hand. While arranging cards you’ll place the first card in your hand. After picking the second card you’ll compare it with the existing card and place it in the correct order. In the same way, the insertion sort algorithm divides the array into two parts, i.e., sorted and unsorted.

Insertion Sort C++ Implementation

Now you might be thinking how can we find a sorted part in an unsorted array. If you look carefully, we can consider the first element of the array as the sorted part and the rest of the array as the unsorted part. With each iteration, we’ll compare the element in the unsorted part with the elements in the sorted part. Hence as we move forward the array gets sorted. It is a stable algorithm as it preserves the order of array in case of repetition. Below we have implemented the insertion sort algorithm in C++.

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
//program to sort the vector using insertion sort
void insertionSort(vector<int> &nums){
    int n = nums.size(), i, j, val;
    for(i=1;i<n;i++){//since we consider the first element as sorted we compare it with rest of the array element
        val = nums[i];//current element for comparison
        j = i-1;
        while(j>=0 and nums[j]>val){//this loop executes till we find an appropriate position of val
            nums[j+1] = nums[j];
            j--;
        }
        nums[j+1] = val;
    }
    return;
}

int main()
{
    vector<int> nums;//initializing the vector
    nums.push_back(50);
    nums.push_back(40);
    nums.push_back(30);
    nums.push_back(20);
    nums.push_back(10);
    
    insertionSort(nums);//calling the insertion sort function to sort the vector
    int i;
    for(i=0;i<nums.size();i++){
        cout<<nums[i]<<" ";//printing the element of vector in a sorted manner
    }   
    return 0;
}

Dry Run

Since the first element is considered as the sorted part and the rest of the elements as unsorted, we start the comparison from the second element. For the purpose of visualization, we made the sorted part bold.
50, 40, 30, 20, 10

When i=1, we find 40(i.e., nums[1]) is less than 50(i.e., nums[0]). Therefore, we move 50 and insert 40 at its place.
40, 50, 30, 20, 10

When i=2, we find 30 < 50. Therefore we move 50 to the next position and again compare 30 with 40 to find 30 < 40. So, we move 40 to the next position and insert 30 at its place.
30, 40, 50, 20, 10

Similarly, when i=3 we observe that 20 is smaller than every element in the sorted segment. Therefore we'll insert 20 at the first position and shift other elements in the one position ahead of their current position.
20, 30, 40, 50, 10

Finally, when i=4 we'll move 10 to the beginning of the array and hence we sort the entire array this way.
10, 20, 30, 40, 50

Insertion Sort Time Complexity
Best Case Time Complexity: O(N)
Worst Case Time Complexity:O(N²)

Insertion Sort Space Complexity: O(1) //since we do the sorting in place.
That was all about insertion sort. Hope you liked the article and to read more interesting articles visit Codekyro.
Also read: Window Sliding Technique – An Efficient Technique
Find Peak Element in Array | Leetcode Problem #162