Insertion sort
easyLift each value out, slide the larger ones right, drop it into the gap. On nearly-sorted input the inner loop barely runs - which is why real library sorts fall back to it for small or partly-ordered runs.
O(n)Average O(n²)Worst O(n²)Space O(1)StableIn placeSaved in this browser - no sign-up, nothing sent anywhere.
How insertion sort works
Sort the way you sort a hand of cards: the left part of the array is always ordered, and each new value is lifted out, larger values slide one slot right, and the value drops into the gap. After processing index i, a[0..i] is sorted among itself - not final positions yet, but always ordered.
It is adaptive: each element moves past only the elements greater than it. On nearly-sorted input the inner while loop barely runs and the cost collapses to about n comparisons - run the nearly-sorted preset and watch it. This is exactly why Timsort and introsort hand runs below a few dozen elements to insertion sort.
This implementation shifts rather than swaps: the key is read once, each displaced element is written once, and the key is written once at the end. Bubble sort pays two writes per swap to move a value one slot; that difference is why insertion sort wins in practice among the quadratic sorts. The strict a[j] > key comparison stops at equals, keeping it stable.
Step by step
- Sort [7, 3, 9, 4, 8]. Lift out the key 3; the sorted region is just [7].
- 7 > 3, so 7 shifts right and 3 drops into index 0: [3, 7, 9, 4, 8].
- Key 9: the first comparison finds 7 <= 9, so 9 is already placed. One comparison, zero shifts.
- Key 4: 9 and 7 both shift right, 3 stops the scan, and 4 lands at index 1: [3, 4, 7, 9, 8].
- Key 8: 9 shifts, 7 <= 8 stops the scan, 8 drops into index 3: [3, 4, 7, 8, 9].
- Sorted in 7 comparisons. The same values reversed would cost 10 - the gap between those numbers is the adaptivity.
Complexity
| Best case time | O(n) |
|---|---|
| Average time | O(n²) |
| Worst case time | O(n²) |
| Space | O(1) |
Each element moves past only the elements greater than it.
Reference implementation
Python
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j] # shift right
j -= 1
a[j + 1] = key # drop the key in
return aJavaScript
function insertionSort(a) {
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]; // shift right
j--;
}
a[j + 1] = key; // drop the key in
}
return a;
}Java
static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]; // shift right
j--;
}
a[j + 1] = key; // drop the key in
}
}C++
void insertionSort(vector<int>& a) {
for (int i = 1; i < (int)a.size(); i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]; // shift right
j--;
}
a[j + 1] = key; // drop the key in
}
}Worth noticing
This is how you sort a hand of cards
The left region is always sorted. Each new card is lifted out, the bigger cards slide right to open a gap, and the card drops into it. Nothing about the algorithm is more complicated than that.
Nearly-sorted input is close to linear
Run the 'nearly sorted' preset: the inner while loop almost never executes, so the cost collapses to about n comparisons. This is exactly why real library sorts (Timsort, introsort) fall back to insertion sort on small or nearly-ordered runs.
Shifts, not swaps
A swap is two writes; a shift is one. Insertion sort moves each displaced element once instead of bubbling it, which is why it beats bubble sort in practice even though both are O(n²).
Common pitfalls
- Swapping adjacent pairs downward instead of shift-then-drop. The result is right, but every move costs two writes instead of one - the counter here counts writes for exactly this reason.
- Shifting on a[j] >= key instead of strict >. Equal elements slide past each other and stability quietly breaks, which matters the moment you sort by a second key.
- Testing a[j] > key before j >= 0. C reads out of bounds; JavaScript coerces undefined, evaluates false, and masks the bug until the port.
- Binary-searching the insert position and claiming O(n log n). The search saves comparisons, but the shifts still cost O(n) per element - the sort stays quadratic.
- Reaching for it at scale: 100,000 random values mean roughly 2.5 billion comparisons. Its niche is small or nearly-ordered input, not general data.
Where it is used
- The small-run workhorse inside Timsort - Python's sorted, Java's Arrays.sort for objects - and C++ introsort, typically below 16 to 32 elements.
- Online sorting: keeping a list ordered as values arrive one at a time, each insertion touching only what it must.
- Nearly-sorted streams - log lines with slight timestamp jitter, or re-sorting data after small edits.
- The interview baseline for adaptive sorting and the k-sorted array discussion.
Frequently asked questions
What is the time and space complexity of insertion sort?
Best case O(n) on sorted input - one comparison per element and no shifts. Average and worst case O(n²), because each element moves past every element greater than it, up to n(n-1)/2 total. Space is O(1): it shifts within the array, holding one key aside.
Why is insertion sort faster than bubble sort if both are O(n squared)?
The constant factor is writes. Insertion sort moves each displaced element with a single write and drops the key once; bubble sort moves values by swapping, two writes per step. Same comparison order of growth, roughly half the memory traffic - which is why libraries embed insertion sort and never bubble sort.
Is insertion sort stable?
Yes. The inner loop shifts only while a[j] is strictly greater than the key, so the scan stops at the first equal value and the key lands after it - original order preserved. Writing the comparison as >= is the one-character change that destroys this.
Why do quicksort and merge sort implementations switch to insertion sort for small arrays?
Below a few dozen elements, constant factors beat asymptotics. Insertion sort has no recursion, no allocation, and a tight sequential inner loop that caches love - and small runs are often partly ordered, its best case. Timsort and introsort both cut over around 16 to 32 elements.