Insertion Sort — Algorithm Visualized
Learn insertion sort — build sorted prefix one element at a time, O(n) best case on nearly sorted data, interactive bar chart visualizer.
Introduction
Insertion sort works like sorting playing cards in your hand — take the next card and insert it into the correct position in the already-sorted portion. Excellent on small or nearly sorted arrays; worst case O(n²).
Quick index
| # | Section |
|---|---|
| 1 | How it works |
| 2 | Interactive visualizer |
| 3 | Full implementation |
| 4 | Complexity analysis |
| 5 | Real-life examples |
1. How it works
Sorted: [3, 5, 8] | Next: 1
→ shift 8,5,3 right → insert 1 → [1, 3, 5, 8]2. Interactive visualizer
Insertion Sort — Step Visualizer
Build a sorted prefix by inserting each next element into its correct position.
Unsorted
n = 7 elements
Step 1 — Sorted prefix = [arr[0]]
for (let i = 1; i < n; i++) key = arr[i]; shift larger right; insert key
Grow sorted region one element at a time.
Time
O(n²)
Space
O(1)
Stable
Yes
3. Full implementation
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i]
let j = i - 1
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
return arr
}Function calls with output
// ── Demo calls — output shown on the right ──
const arr = [5, 3, 8, 1, 9, 2, 7]
insertionSort(arr) // → [1, 2, 3, 5, 7, 8, 9]
insertionSort([1, 2, 3, 4]) // → [1, 2, 3, 4] (best case O(n))4. Complexity analysis
| Case | Time |
|---|---|
| Best | O(n) — already sorted |
| Average | O(n²) |
| Worst | O(n²) — reverse sorted |
| Space | O(1) |
| Stable | Yes |
5. Real-life examples
| Scenario | Why insertion sort |
|---|---|
| Sorting cards in your hand | Each new card slides into the correct spot — exactly insertion sort |
| Nearly sorted log files | Timestamps mostly in order — O(n) best case |
| Live leaderboard updates | One new score inserted into sorted top-100 list |
| Timsort subarrays (V8/Node) | JavaScript's Array.sort() uses insertion sort for small n |
| Adding one row to sorted spreadsheet | Shift-right + insert one value |
Live sports leaderboard
Insert one new score into a nearly sorted top-10 list — insertion sort shines.
Index → value
Already sorted descending — best case friendly.
Real-world implementation
function insertionSort(arr) {
const a = [...arr]
for (let i = 1; i < a.length; i++) {
const key = a[i]
let j = i - 1
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]
j--
}
a[j + 1] = key
}
return a
}Full working code for the scenario above.
Function calls with output
// ── Function calls with output ── const topScores = [980, 920, 890, 850, 800, 760, 720, 680, 650, 620]
Side output shows return value after each call — step through to trace execution.
Summary
Insertion sort is adaptive — O(n) when input is almost sorted — and stable. Great for small n.
Next reads: Merge Sort · Quick Sort
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime