Insertion Sort

What is Insertion Sort?

Insertion sort is a comparison-based algorithm that builds a final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, its simplicity makes it advantageous for small datasets and provides a foundational understanding of how sorting works.

How Does Insertion Sort Work?

The algorithm works by iterating through each element in the array, growing a sorted sublist behind the current location. Here’s a detailed breakdown:

Start from the second element: Assume the first element is already sorted. Compare the current element with the sorted elements: Move all elements that are greater than the current element one position ahead. Insert the current element at its correct position. Repeat for all elements.

Implementation

void insertionSort(vector<int>& arr) {
    int i, key, j;
    int n = arr.size();
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // Move elements of arr[0..i-1], that are greater than key,
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Step by Step Example

Analysis of Insertion Sort

Unlike selection sort, there is a huge difference between the best case (input is sorted in the desired order), and the worst case (the input is sorted in the opposite order). The runtime complexity would be linear for the best case and quadratic for the second one. Here is an explaination: