Insertion Sort

A sorting technique that builds the sorted array one element at a time, inserting each new element into its proper position among already-sorted elements.

Time complexity is Quadratic, i.e. O(n^2)
Space complexity is Constant, i.e. O(1)

export function insertionSort(numbersArray: number[]): void {
  let currentIndex: number;
  let currentKey: number;
  let previousIndex: number;

  for (currentIndex = 1; currentIndex < numbersArray.length; currentIndex++) {
    currentKey = numbersArray[currentIndex];
    previousIndex = currentIndex - 1;

    // Move elements that are greater than currentKey one position ahead.
    while (previousIndex >= 0 && numbersArray[previousIndex] > currentKey) {
      numbersArray[previousIndex + 1] = numbersArray[previousIndex];
      previousIndex--;
    }

    numbersArray[previousIndex + 1] = currentKey;
  }
}

import { describe, test, expect } from "bun:test";
import { insertionSort } from "./code";

describe("Insertion Sort", () => {
  test("Sort", () => {
    const a = [5, 2, 4, 6, 1, 3];
    insertionSort(a);
    expect(a.toString()).toBe("1,2,3,4,5,6");
  });
});

Identity Combinator

Intercepting Filter

Docs

computer-science.dev

Title here

Insertion Sort