Insertion Sort

Insertion sort is a sorting algorithm that while quite inefficient, is really simple to implement. In principle, it involves looping over the array, checking if the current value is greater than the previous value, and if it isn’t we insert it into the ‘correct’ spot of the previously sorted values.

Invariant

The invariant of an insertion sort is that at the start of the loop all elements to the left of the current iteration ($i$), are already sorted.

Implementation

#include <iostream>  
  
int array[] = {1, 4, 2, 9, 3, 0};  
int n = sizeof(array) / sizeof(array[0]);  
  
int main() {  
    int i = 1; // i starts at the second element  
    for(i; i < n; i++) { //for each element in the array  
        int key = array[i]; //we assign the element to be swapped at i  
        int j = i - 1; // we assign the previous index j, the start of the array to be checked against  
        while(j >= 0 && key < array[j]) { //we then perform an insert on the already sorted array  
            array[j + 1] = array[j]; // we shift elements to the right. This overwrites the value to be shifted, so that's why we need to keep it in the key local.  
            j--; //decrement, we're going backwards into the already sorted array  
        }  
  
        array[j + 1] = key; // we reinsert it when the loop is done, i.e j represents the value of the value where key < j is no longer true  
    }  
    
    for(int i = 0; i < n; i ++) {  
        std::cout << "Array is: " << array[i] << std::endl;  
    }  
  
}

Complexity

The time complexity of insertion sort is amongst the worst possible complexities for common sorting algorithms, with a worst case of:

$$O(n^2)$$

Conceptually, this is due to the algorithm having to iterate twice over the length of the data. It iterates once per element, and for each element it will iterate over the entirety of the left already sorted side of the list.

This is why for the most part, aside from educational purposes insertion sort is rarely used in practice.