Insertion Sort

1. Insertion Sort Algorithm
2. Insertion Sort Example
3. Insertion Sort Algorithm Implementation
4. Insertion Sort Algorithm Complexity

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.

Insertion Sort Example

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

• First Iteration

Key : A[1] = 3

• Second Iteration

Key : A[2] = 4

• Third Iteration

Key : A[3] = 2

• Fourth Iteration

Key : A[4] = 1

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(n²).

• 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(n²).

• 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.