Quick Sort

About

It's a Divide and Conquer algorithm. It takes a pivot value that usually is in the middle of the DS, and sorts every value smaller or equal than the pivot to it's left and every value greater to the right.

After this, you take a new pivot for each of the new sections, and do it again, and on and on... until reaching the base case of a section of size 0 or 1.

It should do the sorting inplace, instead of creating temporary structures to hold these middle arrays.

Asymptotically QuickSort can be $O(N\ log N)$ or $O(N²)$ depending on how you pick your pivots.

The literal wort case scenario would be having a reverse ordered Array and picking the last element as the pivot.

Implementation on Arrays

recursive

function partition(arr: number[], lo: number, hi: number): number {
    const pivot = Math.floor((lo + hi) / 2);
    let idx = lo - 1;
    
    for (let i = lo; i < hi; i++) {
        if (arr[i] <= arr[pivot]) {
            idx++;
            const temp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = temp;
        }
    }
    
    idx++;
    arr[hi] = arr[idx];
    arr[idx] = arr[pivot];
    
    return idx;
}

function quickSort(arr: number[], lo: number, hi: number): void {
    if (lo >= hi) return;
    const pivotIdx = partition(arr, lo, hi);
    
    quickSort(arr, lo, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, hi);
}

quickSort(arr, 0, arr.length - 1);