Insertion Sort explained step-by-step: card sorting analogy, element shifting, online sorting capability, adaptive O(n) best case, and JavaScript code.
Insertion Sort works the same way humans naturally sort a hand of playing cards. You start with an empty or single-card left hand, draw one card at a time from the table, and slide it into its correct relative position among the cards already sorted in your hand.
Insertion Sort is an adaptive, online algorithm: it can sort a live data stream as items arrive in real time without needing the full array upfront. Because it runs in O(n) linear time for nearly sorted arrays and has tiny constant factor overhead, advanced hybrid sorting algorithms (such as Timsort in Python/Java and Introsort in C++ std::sort) switch to Insertion Sort once subarrays become small (typically n ≤ 16).
Start at index 1 (the second element) and save arr[i] into a variable key. The sub-array arr[0..i-1] is already sorted.
Compare key with elements in the sorted prefix, moving from right to left (index j = i - 1 down to 0).
For every element arr[j] greater than key, shift it one position to the right (arr[j + 1] = arr[j]) to make room.
Place key into the vacated slot at arr[j + 1]. Increment i and repeat until the entire array is sorted.
1function insertionSort(arr) {2 const n = arr.length;3 4 for (let i = 1; i < n; i++) {5 let key = arr[i];6 let j = i - 1;7 8 // Shift elements of arr[0..i-1] that are greater than key to one position ahead9 while (j >= 0 && arr[j] > key) {10 arr[j + 1] = arr[j];11 j--;12 }13 14 arr[j + 1] = key;15 }16 17 return arr;18}19 20// Example usage:21// insertionSort([12, 11, 13, 5, 6]); // [5, 6, 11, 12, 13]Play through every comparison, swap, and state change, adjust the speed, or enter custom inputs to test edge cases.
The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
Explore the full catalog — 30+ algorithms with more unlocking every release.
Ready — press Play or use step controls to walk through the algorithm.
Comparisons
0
Swaps / Shifts
0
Passes / Depth
0
Elements
10
Test your understanding of Insertion Sort complexity and step mechanics.
Q1.What is the best-case time complexity of Insertion Sort for an already sorted array?
Q2.Why is Insertion Sort widely used as the base case in hybrid algorithms like Timsort and Introsort?
Apply Insertion Sort to real coding interview questions.
Sort a singly linked list using the insertion sort algorithm.