Insertion Sort

Harshit Jindal Oct 12, 2023
  1. Insertion Sort Algorithm
  2. Insertion Sort Example
  3. Insertion Sort Algorithm Implementation
  4. Insertion Sort Algorithm Complexity
Insertion Sort

Insertion sort is a simple comparison-based sorting algorithm. In this algorithm, we maintain two subarrays: a sorted and an unsorted subarray. One element from the unsorted subarray finds its correct position in the sorted subarray and gets inserted there. It is analogous to the way when someone sorts a deck of cards in their hand. It is named insertion sort because it works on inserting an element at its correct position. This algorithm is efficient for small datasets but not suitable for large datasets.

Insertion Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements. The first element, A[0], is already sorted and in the sorted subarray.

  • We mark the first element from the unsorted subarray A[1] as the key.
  • The key is then compared with elements from the sorted subarray; here, we have only one element, A[0].
  • If the key is greater than A[0], we insert it after A[0].
  • Else if it is smaller, we compare again to insert it at the correct position before A[0]. (In case of A[0], there is only one position)
  • Take the next element A[2] as key. Compare it with sorted subarray elements and insert after the element just smaller than A[2]. If there are no small elements, then insert it at the beginning of the sorted subarray.
  • Repeat the above steps for all the elements in the unsorted subarray.

Insertion Sort Example

Suppose we have the array: (5,3,4,2,1). We will sort it using the insertion sort algorithm.

Sorted subarray Unsorted Subarray Array
( 5 ) ( 3, 4, 2, 1) (5, 3, 4, 2, 1)
  • First Iteration

Key : A[1] = 3

Sorted subarray Unsorted Subarray Array
( 3 , 5) (4, 2, 1) (3, 5, 4, 2, 1)
  • Second Iteration

Key : A[2] = 4

Sorted subarray Unsorted Subarray Array
( 3, 4, 5) (2, 1) (3, 4, 5, 2, 1)
  • Third Iteration

Key : A[3] = 2

Sorted subarray Unsorted Subarray Array
( 2, 3, 4, 5) (1) (2, 3, 4, 5, 1)
  • Fourth Iteration

Key : A[4] = 1

Sorted subarray Unsorted Subarray Array
( 1, 2, 3, 4, 5) () (1, 2, 3, 4, 5)

Insertion Sort Algorithm Implementation

#include <iostream>
using namespace std;

void insertion_sort(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
      int key = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = key;
      j--;
    }
  }
}

int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  insertion_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Insertion Sort Algorithm Complexity

Time Complexity

  • Average Case

On average, i comparisons are made in the ith pass of insertion sort. So if there are n iterations, then the average time complexity can be given below.

1 + 2 + 3 + ... + (n-1) = n*(n-1)/2

Hence the time complexity is of the order of [Big Theta]: O(n2).

  • Worst Case

The worst-case occurs when the array is reversely sorted, and the maximum number of comparisons and swapping has to be performed.

The worst-case time complexity is [Big O]: O(n2).

  • Best Case

The best-case occurs when the array is already sorted, and then only the outer loop is executed n times.

The best-case time complexity is [Big Omega]: O(n).

Space Complexity

Space Complexity for the insertion sort algorithm is O(n) because no extra memory other than a temporary variable is required.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Related Article - Sort Algorithm