64
34
25
12
22
11
90
0
1
2
3
4
5
6
Starting Insertion Sort. The first element is trivially sorted.
Presets:
Size:
Timeline Progress:
0%Step 1 / 42
Comparisons
0
Swaps / Actions
0
Speed:
Shortcuts: Space Play ā¢ ā/ā Step ā¢ R Reset ā¢ M Sound ā¢ Z Focus
Implementation Code
1
2
3
4
5
6
7
8
9
10
11
12
13
function insertionSort(arr: number[]): number[] {
const n = arr.length;
for (let i = 1; i < n; 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;
}Complexity Analysis
Best Case
O(n)
Average Case
O(nĀ²)
Worst Case
O(nĀ²)
Space
O(1)
StableIn-Place
Color Legend
Unsorted
Comparing
Swapping
Sorted
Insertion Sort builds the final sorted array one element at a time. It takes each element from the unsorted part and finds its correct position within the sorted part by shifting larger elements to the right. It is efficient for small datasets and nearly-sorted data, and is the algorithm of choice for sorting small arrays in practice.