Insertion Sort: Algorithm, Dry Run, Code & Complexity Explained
What is Insertion Sort?
Insertion Sort builds the sorted array one element at a time — just like sorting playing cards in your hand. It picks each element as a key and inserts it into its correct position among the already-sorted elements by shifting larger elements right.
Algorithm Steps
- Start at index 1 (index 0 is trivially sorted)
- Store the current element as key
- Compare key with elements to its left, shifting them right while arr[j] > key
- Insert key at the gap left behind
- Repeat for all remaining elements
Code Implementation
🐍 Python
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i] # element to insert
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift right
j -= 1
arr[j + 1] = key # insert at correct position
return arr☕ Java
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // shift right
j--;
}
arr[j + 1] = key; // insert
}
}
}⚙️ C++
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // shift right
j--;
}
arr[j + 1] = key; // insert
}
}
🟡 JavaScript
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // shift right
j--;
}
arr[j + 1] = key; // insert
}
return arr;
}
console.log(insertionSort([20, 10, 35, 2, 15, 30]));
// Output: [2, 10, 15, 20, 30, 35]Dry Run — arr = [20, 10, 35, 2, 15, 30]
Key (being inserted)
Shifting right
Sorted portion
Pass 1 (i=1) — key = 10
| j | arr[j] | arr[j] > key (10)? | Action |
|---|---|---|---|
| 0 | 20 | ✅ Yes | Shift 20 → arr[1] = 20 |
| -1 | — | Loop ends | Insert 10 → arr[0] = 10 |
10
inserted
20
sorted
35
idx 2
2
idx 3
15
idx 4
30
idx 5
Pass 2 (i=2) — key = 35
20 < 35 — loop doesn't execute. 35 stays in place.
10
sorted
20
sorted
35
no move
2
idx 3
15
idx 4
30
idx 5
Pass 3 (i=3) — key = 2
| j | arr[j] | arr[j] > key (2)? | Action |
|---|---|---|---|
| 2 | 35 | ✅ Yes | Shift 35 → arr[3] |
| 1 | 20 | ✅ Yes | Shift 20 → arr[2] |
| 0 | 10 | ✅ Yes | Shift 10 → arr[1] |
| -1 | — | Loop ends | Insert 2 → arr[0] |
2
inserted
10
shifted
20
shifted
35
shifted
15
idx 4
30
idx 5
Pass 4 (i=4) — key = 15
| j | arr[j] | arr[j] > key (15)? | Action |
|---|---|---|---|
| 3 | 35 | ✅ Yes | Shift 35 → arr[4] |
| 2 | 20 | ✅ Yes | Shift 20 → arr[3] |
| 1 | 10 | ❌ No | Loop ends, insert 15 → arr[2] |
2
sorted
10
sorted
15
inserted
20
shifted
35
shifted
30
idx 5
Pass 5 (i=5) — key = 30
| j | arr[j] | arr[j] > key (30)? | Action |
|---|---|---|---|
| 4 | 35 | ✅ Yes | Shift 35 → arr[5] |
| 3 | 20 | ❌ No | Loop ends, insert 30 → arr[4] |
2
idx 0 ✓
10
idx 1 ✓
15
idx 2 ✓
20
idx 3 ✓
30
idx 4 ✓
35
idx 5 ✓
🎉 Sorted: [2, 10, 15, 20, 30, 35]
Time & Space Complexity
| Case | Time | Reason |
|---|---|---|
| Best | O(n) | Already sorted — inner while never runs |
| Average | O(n²) | Random order — partial shifts |
| Worst | O(n²) | Reverse sorted — max shifts every pass |
| Space | O(1) | In-place — only key and j variables |
Is Insertion Sort Stable?
✅ Yes. We only shift elements that are strictly greater than key. Equal elements are never moved past each other, preserving their relative order.
Final Comparison: All Three O(n²) Sorts
| Property | Bubble Sort | Selection Sort | Insertion Sort |
|---|---|---|---|
| Best Case | O(n) | O(n²) | O(n) ★ |
| Average | O(n²) | O(n²) | O(n²) |
| Worst | O(n²) | O(n²) | O(n²) |
| Stable? | ✅ Yes | ❌ No | ✅ Yes |
| Adaptive? | ✅ Yes | ❌ No | ✅ Best |
Insertion Sort is used inside Timsort — Python's built-in sort — for small arrays under 64 elements. It's the most practical of the three.