Insertion Sort Algorithm in DSA C++

Mental Model

Insertion sort builds a sorted list by taking one item at a time and placing it in the right spot among the already sorted items.

Analogy: Imagine sorting playing cards in your hand: you pick one card and insert it into the correct position among the cards you already hold sorted.

Unsorted array: [5, 3, 8, 6, 2]
Sorted part ↑
[5] 3 8 6 2

Dry Run Walkthrough

Input: array: [5, 3, 8, 6, 2]

Goal: Sort the array in ascending order using insertion sort

Step 1: Start with second element 3, compare with 5 and shift 5 right

[3, 5, 8, 6, 2]

Why: We insert 3 before 5 to keep the sorted part correct

Step 2: Move to element 8, it is already greater than 5, so no change

[3, 5, 8, 6, 2]

Why: 8 is in correct position relative to sorted part

Step 3: Take 6, compare with 8 and shift 8 right, then insert 6

[3, 5, 6, 8, 2]

Why: 6 fits between 5 and 8, so 8 moves right

Step 4: Take 2, shift 8, 6, 5, 3 right and insert 2 at start

[2, 3, 5, 6, 8]

Why: 2 is smallest, so it moves to front

Result:

Sorted array: [2, 3, 5, 6, 8]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // Move elements greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // Insert key at correct position
    }
}

int main() {
    vector<int> arr = {5, 3, 8, 6, 2};
    insertionSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

for (int i = 1; i < n; i++) {

iterate over each element starting from second to insert it in sorted part

int key = arr[i];

store current element to insert

int j = i - 1;

start comparing with previous elements

while (j >= 0 && arr[j] > key) {

shift elements greater than key to the right

arr[j + 1] = arr[j];

move element one step right to make space

j--;

move left to continue checking

arr[j + 1] = key;

insert key at correct sorted position

Output

2 3 5 6 8 

Complexity Analysis

Time: O(n^2) because in worst case each element is compared with all previous elements

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Insertion sort is simpler but slower than efficient sorts like quicksort (O(n log n)), but better for small or nearly sorted data

Edge Cases

empty array

function returns immediately without changes

DSA C++

for (int i = 1; i < n; i++) {

array with one element

no sorting needed, array remains same

DSA C++

for (int i = 1; i < n; i++) {

array already sorted

minimal shifts, runs in O(n) time

DSA C++

while (j >= 0 && arr[j] > key) {

When to Use This Pattern

When you need to sort a small or nearly sorted list and want a simple method, reach for insertion sort because it inserts elements one by one in order.

Common Mistakes

Mistake: Not shifting elements before inserting key, causing overwriting
Fix: Shift all elements greater than key one position right before placing key

Mistake: Starting loop from index 0 instead of 1
Fix: Start from second element since first is trivially sorted

Summary

Insertion sort builds a sorted array by inserting each element into its correct place.

Use it for small or nearly sorted arrays where simplicity and low overhead matter.

The key insight is shifting larger elements right to make space for the current element.