Insertion Sort Algorithm

What is Insertion Sort?

Insertion Sort is a straightforward, intuitive comparison-based sorting algorithm. It works similarly to how you might sort a hand of playing cards: pick one card at a time and insert it into its correct position among the already sorted cards.

Insertion Sort is particularly efficient for small datasets and nearly sorted arrays, and it is known for being simple, stable, and easy to implement.

How Insertion Sort Works

1. Start from the second element (first one is considered sorted).
2. Compare it with the elements before it.
3. Shift all larger elements one position to the right.
4. Insert the current element at its correct position.
5. Repeat for all elements.

With each pass, the left portion of the array becomes increasingly sorted.

Time & Space Complexity

• Space Complexity: O(1) → In-place sort
• Stable: ✅ Yes

When to Use Insertion Sort

• For small datasets
• When the array is nearly sorted
• When a stable, in-place sort is required
• In hybrid sorting algorithms like Timsort for sorting small chunks

Insertion Sort – C++ Code Example

#include <iostream>
using namespace std;

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

        // Shift larger elements to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;

        // Print array after each pass
        cout << "After pass " << i << ": ";
        for (int k = 0; k < n; k++) {
            cout << arr[k] << " ";
        }
        cout << endl;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array:\n";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "Sorted array:\n";
    printArray(arr, n);

    return 0;
}

Output

Original array:
12 11 13 5 6 
After pass 1: 11 12 13 5 6 
After pass 2: 11 12 13 5 6 
After pass 3: 5 11 12 13 6 
After pass 4: 5 6 11 12 13 
Sorted array:
5 6 11 12 13 

Insertion Sort – Visual Explanation (Step-by-Step)

Let’s sort:

[12, 11, 13, 5, 6]

Pass 1: i = 1, key = 11

• Compare 11 with 12 → 11 < 12 → shift 12
• Insert 11 before 12

[11, 12, 13, 5, 6]

Pass 2: i = 2, key = 13

• Compare 13 with 12 → 13 > 12 → no shift needed

[11, 12, 13, 5, 6]

Pass 3: i = 3, key = 5

• Compare 5 with 13 → shift 13
• Compare 5 with 12 → shift 12
• Compare 5 with 11 → shift 11
• Insert 5 at position 0

[5, 11, 12, 13, 6]

Pass 4: i = 4, key = 6

• Compare 6 with 13 → shift 13
• Compare 6 with 12 → shift 12
• Compare 6 with 11 → shift 11
• Insert 6 at position 1

[5, 6, 11, 12, 13]

Final Sorted Array

[5, 6, 11, 12, 13]

Summary

• Insertion Sort is simple and works well on small or nearly sorted datasets.
• It is stable, in-place, and easy to understand.
• Performs better than other O(n²) sorts in many practical situations.