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.

/**
 * @file Insertion Sort
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Sorts an array of numbers in ascending order using the insertion sort
 * algorithm.
 *
 * @param numbersArray - The array of numbers to be sorted.
 */
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;
  }
}

// Usage example
(() => {
  const numbersArray = [5, 2, 4, 6, 1, 3];
  insertionSort(numbersArray);

if (numbersArray.toString() !== '1,2,3,4,5,6') {
    throw new Error(
      `Test failed: ${numbersArray.toString()} is not sorted correctly.`,
    );
  }

console.log('Sorted array:', numbersArray);
  // Should output: [1, 2, 3, 4, 5, 6]
})();