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.

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

test.ts

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

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