Insertion Sort

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