Insertion Sort
See each element get lifted out, larger values shift right to make room, and the element drop into its place, like sorting a hand of cards.
How it works
Insertion sort builds the sorted part one element at a time, the way you sort a hand of cards. It lifts the next element (the key) out of the unsorted part and compares it with the sorted values to its left, from right to left. Every value larger than the key shifts one step right, opening a gap. As soon as a value is smaller or equal, the key is inserted into the gap and the next element starts.
There are no swaps: each larger value moves once per pass, and the key is written only once, into its final spot in the sorted part. Each pass also stops early once the key finds its spot, so an array that is already nearly sorted takes very few comparisons.
When to use it
Insertion sort is fast on small or nearly sorted arrays, and it is simple and stable. That's why hybrid sorts like Timsort and introsort switch to insertion sort for short runs.
Complexity
It is stable: shifting stops at the first value that is not larger than the key, so the key never passes an equal value.
| Case | Time | When |
|---|---|---|
| Best | O(n) | Already sorted: one comparison per element, no shifts |
| Average | O(n²) | Random order |
| Worst | O(n²) | Sorted in reverse: every element shifts to the front |
| Extra space | Why |
|---|---|
| O(1) | It shifts values in place, holding only the key and a few loop variables |
Implementations
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
const key = array[i];
let j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
return array;
}
def insertion_sort(array):
a = list(array)
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]
j -= 1
a[j + 1] = key
return a
#include <vector>
std::vector<int> insertionSort(std::vector<int> a) {
const int n = static_cast<int>(a.size());
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
return a;
}