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)

Source Code Listing

code.ts

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;
  }
}

code_test.ts

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");
  });
});

Tags: