Pattern visualizer
Insertion Sort
The key insight: insertion sort builds the sorted array one element at a time, from left to right. In each pass, we take the next element and shift larger elements in the sorted prefix one position to the right, creating a hole where the new element belongs. This is like sorting playing cards in your hand: pick up one card, compare it to the ones already held, and insert it in the correct position. Animated on: Sort nums = [5, 2, 4, 6, 1, 3] in ascending order using insertion sort..
Sorting
time O(n^2)space O(1)step 1 / 33
5
[0]2
[1]4
[2]6
[3]1
[4]3
[5]line 3
i = 1: pick up arr[i] = 2 as the key; the sorted prefix so far is just [5] to the left of index 1.
Pseudocode
1FUNCTION insertionSort(arr):2 n = the length of arr3 FOR i from 1 to n-1:4 key = arr[i] (the value to insert)5 j = i - 16 WHILE j >= 0 and arr[j] > key:7 arr[j + 1] = arr[j] (shift the bigger value one step right)8 j = j - 19 arr[j + 1] = key (drop key into the hole)
← / → step · space play · Home restart