[Algorithms] Merge Sort - TypeScript Implementation

algorithm-mergeSort.ts

/**
 *  @file algorithm-mergeSort.ts - A TypeScript implementation of the Merge Sort algorithm using recursion
 *  @author Avana Vana
 *  @desc Algorithmic complexity:
 *  - Time complexity: 	Ω(n log(n)), Θ(n log(n)), O(n log(n))	
 *  - Space complexity: O(n)
 */

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

function mergeSort<T>(arr: T[]): T[] {
    if (arr.length === 1) return arr;
    let mid = Math.floor(arr.length / 2)
    return merge(mergeSort(arr.slice(0, mid), mergeSort(arr.slice(mid));
}
                                                                                     
/**
 *  @function merge
 *  @desc Helper function to combine arrays split by the recursive function {@link mergeSort} 
 *  @template T
 *  @param {T[]} left - the left-hand half of an input array of type T
 *  @param {T[]} right - the right-hand half of an input array of type T
 *  @returns {T[]} a merged and sorted array of type T
 */
                                                                                     
function merge<T>(left: T[], right: T[]): T[] {
    let sorted: T[] = [];
  
    while (left.length && right.length) {
        if (left[0] < right[0]) sorted.push(left.shift() as T);
        else sorted.push(right.shift() as T);
    }
                              
    return [ ...sorted, ...left, ...right ];
}

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

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