[Algorithms] Insertion Sort - TypeScript Implementation

algorithm-insertionSort.ts

/**
 *  @file algorithm-insertionSort.ts - A TypeScript implementation of the Insertion Sort algorithm
 *  @author Avana Vana
 *  @desc Algorithmic complexity:
 *  - Time complexity: Ω(n), Θ(n^2), O(n^2)
 *  - Space complexity: O(1)
 */

/**
 *  @function insertionSort
 *  @desc Sorts an input array according to the Insertion Sort algorithm and returns the sorted array
 *  @template T
 *  @param {T[]} arr - input array of type T
 *  @returns {T[]} Sorted input array
 */

function insertionSort<T>(arr: T[]): T[] {
    for (let i = 1; i < arr.length; i++) {
        let currentItem = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > currentItem) arr[j + 1] = arr[j--];
        arr[j + 1] = currentItem;
    }
  
    return arr;
}

insertionSort([ 3, 7, 5, 2, 6, 1, 0, 4 ]);

// > [ 0, 1, 2, 3, 4, 5, 6, 7 ]