Insertion Sort — Build Sorted Region One Element at a Time

What does it solve?

Sort an array by building a sorted region on the left, one element at a time. At each step, take the next unsorted element (the "key") and shift it backward through the sorted region until it lands in its correct position.

Think of sorting playing cards in your hand — you pick up one card and slide it into the right spot among the cards you've already sorted.

The algorithm

// i starts at 1: arr[0] is trivially sorted
for i = 1 to n-1:
  key = arr[i]
  j = i - 1
  // shift larger elements right
  while j >= 0 and arr[j] > key:
    arr[j+1] = arr[j]
    j--
  arr[j+1] = key

💡 Key insight: Unlike Bubble Sort which compares neighboring pairs blindly, Insertion Sort only shifts elements that are actually larger than the key — it stops as soon as it finds an element ≤ key. This makes it extremely fast on nearly sorted data (close to O(n)), which is why it's often used as the base case in hybrid algorithms like Timsort.

Complexity

Best case

O(n)

Already sorted — each key needs zero shifts, just one comparison.

Average / Worst

O(n²)

Reverse sorted — every key shifts all the way to the front.

Space

O(1)

Sorts in-place; only the `key` variable is extra storage.

Examples & edge cases

Live animation — Cards-in-Hand Insertion

Sorted region Key (being inserted) Shifting right Unsorted region

⏸ Waiting to start

🟢 Sorted: —

🟣 Key: —

⚪ Unsorted: —

Step — of —

Key value

—

arr[i]

Comparisons

so far

Shifts

so far

Sorted count

from left

Select an example and press Play to begin.

✓ Sorted!

Speed Medium

Step-by-step table

Step	i	Key	j	Action	Array state

C++ implementation

insertion_sort.cpp

#include <bits/stdc++.h>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();

    // arr[0] is trivially sorted — start from index 1
    for (int i = 1; i < n; i++) {
        int key = arr[i];   // element to insert
        int j = i - 1;

        // Shift all elements greater than key one position right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // Place key in its correct position
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6};
    insertionSort(arr);
    for (int x : arr) cout << x << " "; // 5 6 11 12 13
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars