Insertion Sort Algorithm Explained
Insertion sort builds a sorted portion of the list one element at a time, repeatedly taking the next unsorted element and inserting it into its correct posit...
Published November 15, 2026
Insertion sort builds a sorted list one item at a time by inserting each new item into its correct place among the already sorted ones, like sorting playing cards in your hand. It is O(n²) but excellent for small or nearly sorted data.
The concept
Keep a sorted prefix. Take the next item and shift larger items right until you find its spot.
On nearly sorted input it runs close to O(n), which is why hybrid algorithms like Timsort use it for small chunks.
Insert 3 into [5, 8]
- Sorted prefix: [5, 8], next item: 3
- 8 > 3 → shift right
- 5 > 3 → shift right
- Place 3 at the front: [3, 5, 8]
Practical examples
JavaScript
function insertion(a) {
a = [...a]
for (let i = 1; i < a.length; i++) {
const x = a[i]; let j = i - 1
while (j >= 0 && a[j] > x) { a[j + 1] = a[j]; j-- }
a[j + 1] = x
}
return a
}Python
def insertion(a):
for i in range(1, len(a)):
x, j = a[i], i - 1
while j >= 0 and a[j] > x:
a[j+1] = a[j]; j -= 1
a[j+1] = x
return aComplexity
best O(n) · average/worst O(n²) · space O(1) · stableCommon mistakes
- Swapping repeatedly instead of shifting.
- Off-by-one on the inner loop.
- Using it on large random data.
Key takeaways
- Insert into a sorted prefix.
- Great for small or nearly sorted lists.
- Stable, in-place.
FAQ
Why is it used inside Timsort?
It is fast on small runs and nearly sorted data.
Insertion vs selection sort?
Insertion adapts to sorted input; selection always does the same work.