Insertion sort is a type of sorting algorithm that sorts the list of given items by delivering at least one item in each iteration to its respective place. It is an in-place comparison-based stable sorting algorithm.


Let me elaborate, while insertion sort takes place, the list is divided into two parts. The left end is sorted while the right end is unsorted. At each iteration, one item from the unsorted part is transferred to its correct position in the sorted part.


This is called an incremental design approach since after each iteration we’re one step closer to our solution.

Pseudo Code

mark first element as sortedfor each unsorted element X  ‘extract’ the element X  for j = lastSortedIndex down to 0    if current element j > X      move the sorted element to the right by 1    break the loop and insert X here

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

void insertionSort(int inputArray[], int size) {
    for (int i = 1; i < size; i++) {
        int key = inputArray[i];
        int j = i - 1;
        // Shift elements of inputArray[0..i-1], that are
        // greater than key, to
        // one position ahead of their current position
        while (j >= 0 && inputArray[j] > key) {
            inputArray[j + 1] = inputArray[j];
            j = j - 1;
        }
        inputArray[j + 1] = key;
    }
}
int main() {
    int inputArray[] = {2, 5, 1, 95, 23, 72, 7, 26, 9};
    int size = sizeof(inputArray) / sizeof(inputArray[0]);
    insertionSort(inputArray, size);

    for (int i = 0; i < size; i++) {
        cout << inputArray[i] << " ";
    }
    return 0;
}

Output

1 2 5 7 9 23 26 72 95

Time Complexity

In the above code, we run two nested loops and perform the comparison and shift operations to sort the input. Let’s find out the worst-case and best-case time complexity:


Worst Case Scenario: This will come into play if the given input list is reverse sorted i.e., in decreasing order. Here, the algorithm performs the maximum number of operations.Time Complexity = O(n2)


Best Case Scenario: 
This will come into play if the given input list already sorted i.e., in increasing order. Here, the algorithm performs the minimum number of operations.Time Complexity = O(n)

Space Complexity

This is an in-place sorting algorithm i.e.; we are not using any extra space for running this algorithm, which implies that Auxiliary Space = O(1) & Space used by input = O(n)

Total Space Complexity = O(n)

Practice Problems

For all these problems please write the Insertion Sort algorithm from Scratch, it will help you to understand the Insertion Sort Code from depth. After which you can use C++ STL Function which you will be learning later in this Series.

  1. Insertion Sort – Part 1 (Hackerrank)
  2. Insertion Sort – Part 2 (Hackerrank)
  3. Correctness and the Loop Invariant (Hackerrank)
  4. Running Time of Algorithms (Hackerrank)
  5. Insertion Sort Advanced Analysis (Hackerrank)


If you find any errors in the article, please comment below.

Leave a Reply