Everything is compared to every other item, just as it was with bubble sort. It “splices” in the correct order rather than replacing. In other words, it restores the original arrangement of repeated items.

**The complexity of Space and Time**

Best: O(n) time | O(1) space

Average: O(n^2) time | O(1) space

Worst: O(n^2) time | O(1) space

*n is the length of the input array.*

**Input**

`[8, 5, 1, 9, 5, 6, 2]`

**Output**

`[1, 2, 5, 5, 6, 8, 9]`

**Hint**

Divide the input array into two subarrays; the first subarray should be sorted at all times and while the second subarray should be unsorted. Iterate through the unsorted subarray, inserting all of its elements into the sorted subarray in the correct position by swapping them.

At first, the array will be split into smaller sections. These sections are then combined to form larger ones until eventually the entire array is sorted.

**Pseudo Code**

DEFINE FUNCTION insertionSort(array): FOR i IN range(1, len(array)): SET j TO i WHILE j > 0 and array[j] < array[j - 1]: swap(j, j - 1, array) j -= 1 RETURN array DEFINE FUNCTION swap(i, j, array): SET array[i], array[j] TO array[j], array[i]

**Typescript Code**

function insertionSort(array) { for (let i = 1; i < array.length; i++) { let j = i; while (j > 0 && array[j] < array[j - 1]) { swap(j, j - 1, array); j -= 1; } } return array; } function swap(i, j, array) { const temp = array[j]; array[j] = array[i]; array[i] = temp; } mocha.setup("bdd"); describe("Bubble Sort", () => { it("Test Case #1", function () { const input = [8, 5, 1, 9, 5, 6, 2]; chai.expect(insertionSort(input)).to.deep.equal([1, 2, 5, 5, 6, 8, 9]); }); it("Test Case #2", function () { const input = [5, 3, 1, 2, 4]; chai.expect(insertionSort(input)).to.deep.equal([1, 2, 3, 4, 5]); }); }); mocha.run();

**Demo**

https://codepen.io/evalteam/pen/OJOJGmm

Previous Article

Bubble SortNext Article

Selection SortQuick Sort

January 30, 2022

1 min

Selection Sort

January 28, 2022

1 min

Bubble Sort

January 26, 2022

1 min

Inorder Tree Traversal with No Recursion

September 08, 2022

1 min

Quick Links

Legal Stuff