Quicksort

Reference Code

/**
* @param start inclusive start index
* @param end exclusive end index
*/
function quickSort(list: number[], start: number, end: number) {
    if (start >= end - 1) return;

    const pivotIndex = partition(list, start, end)
    quickSort(list, start, pivotIndex)
    quickSort(list, pivotIndex + 1, end)
}

function partition(list: number[], start: number, end: number): number {
    let swapIndex = start
    for (let i = start; i < end - 1; i++) {
        if (list[i] < list[end - 1]) {
            swap(list, i, swapIndex)
            swapIndex++
        }
    }
    swap(list, swapIndex, end - 1)
    return swapIndex
}