[Algorithms] Quick Sort (Middle Pivot) - TypeScript Implementation

algorithm-quickSortMiddlePivot.ts

/**
 *  @file algorithm-quickSortMiddlePivot.ts - A TypeScript implementation of the Quick Sort algorithm using recursion and the middle element of the input array (or the element just left of center) as a pivot
 *  @author Avana Vana
 *  @desc Algorithmic complexity:
 *  - Time complexity: Ω(n log(n)), Θ(n log(n)), O(n^2) (rare)
 *  - Space complexity: O(n)
 */

/**
 *  @function quickSort
 *  @desc Sorts an input array according to the Quick Sort algorithm with recursion and the pivot set to the middle element (or the element just left of center) and returns the sorted array
 *  @template T
 *  @param {T[]} arr - input array of type T
 *  @returns {T[]} Sorted input array
 */

function quickSort<T>(arr: T[]): T[] {
    if (arr.length <= 1) return arr;
    let pivotIndex = Math.floor(arr.length / 2), left: T[] = [], right: T[] = [];

    for (let i = 0; i < arr.length; i++) {
	if (i === pivotIndex) continue;
	if (arr[i] <= arr[pivotIndex]) left.push(arr[i]);
	else right.push(arr[i]);
    }

    return [ ...quickSort(left), arr[pivotIndex], ...quickSort(right) ];
}

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

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