Algorithm Code
Time: O(n²) | Space: O(1)
1function insertionSort(arr) {
2 for (let i = 1; i < arr.length; i++) {
3 let key = arr[i];
4 let j = i - 1;
5 while (j >= 0 && arr[j] > key) {
6 arr[j + 1] = arr[j];
7 j = j - 1;
8 }
9 arr[j + 1] = key;
10 }
11 return arr;
12}Algorithm Steps
Step 1 of 27
Initial Array
Starting with unsorted array.
Select key arr[1] = 12
Key to insert into sorted portion.
Compare arr[0] (20) > key (12)
Shift arr[0] to arr[1]
Insert key at arr[0]
Key 12 inserted at position 0
Select key arr[2] = 4
Key to insert into sorted portion.
Compare arr[1] (20) > key (4)
Shift arr[1] to arr[2]
Compare arr[0] (12) > key (4)
Shift arr[0] to arr[1]
Insert key at arr[0]
Key 4 inserted at position 0
Select key arr[3] = 13
Key to insert into sorted portion.
Compare arr[2] (20) > key (13)
Shift arr[2] to arr[3]
Insert key at arr[2]
Key 13 inserted at position 2
Select key arr[4] = 5
Key to insert into sorted portion.
Compare arr[3] (20) > key (5)
Shift arr[3] to arr[4]
Compare arr[2] (13) > key (5)
Shift arr[2] to arr[3]
Compare arr[1] (12) > key (5)
Shift arr[1] to arr[2]
Insert key at arr[1]
Key 5 inserted at position 1
Select key arr[5] = 6
Key to insert into sorted portion.
Compare arr[4] (20) > key (6)
Shift arr[4] to arr[5]
Compare arr[3] (13) > key (6)
Shift arr[3] to arr[4]
Compare arr[2] (12) > key (6)
Shift arr[2] to arr[3]
Insert key at arr[2]
Key 6 inserted at position 2
Select key arr[6] = 8
Key to insert into sorted portion.
Compare arr[5] (20) > key (8)
Shift arr[5] to arr[6]
Compare arr[4] (13) > key (8)
Shift arr[4] to arr[5]
Compare arr[3] (12) > key (8)
Shift arr[3] to arr[4]
Insert key at arr[3]
Key 8 inserted at position 3
Done!
Sorted array: [4, 5, 6, 8, 12, 13, 20]