Quick Sort

// 1) Classic Lomuto partition
function quicksort(arr, lo = 0, hi = arr.length - 1) {
    if (lo < hi) {
        const p = partitionLomuto(arr, lo, hi);
        quicksort(arr, lo, p - 1);
        quicksort(arr, p + 1, hi);
    }
    return arr;
}

function partitionLomuto(arr, lo, hi) {
    const pivot = arr[hi];                         // last element as pivot
    let i = lo - 1;
    for (let j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
    return i + 1;
}

// 2) Hoare partition — fewer swaps, slightly trickier
function quicksortHoare(arr, lo = 0, hi = arr.length - 1) {
    if (lo < hi) {
        const p = partitionHoare(arr, lo, hi);
        quicksortHoare(arr, lo, p);
        quicksortHoare(arr, p + 1, hi);
    }
    return arr;
}

function partitionHoare(arr, lo, hi) {
    const pivot = arr[Math.floor((lo + hi) / 2)];
    let i = lo - 1, j = hi + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

// 3) Why pivot strategy matters
// • Last element pivot + sorted input → O(n²) worst case (each partition removes one element)
// • Random pivot → randomised O(n log n) expected; resistant to adversarial inputs
// • Median-of-three → pick pivot from first/middle/last; avoids worst case in practice
// • Median-of-medians → guaranteed O(n log n); expensive constants, rarely used

function medianOfThree(arr, lo, hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < arr[lo])   [arr[lo],  arr[mid]] = [arr[mid],  arr[lo]];
    if (arr[hi] < arr[lo])    [arr[lo],  arr[hi]]  = [arr[hi],  arr[lo]];
    if (arr[hi] < arr[mid])   [arr[mid], arr[hi]]  = [arr[hi],  arr[mid]];
    return arr[mid];
}

// 4) Three-way partition (Dutch national flag) — handles duplicates well
function quicksort3(arr, lo = 0, hi = arr.length - 1) {
    if (lo >= hi) return arr;
    const pivot = arr[lo + ((hi - lo) >> 1)];
    let lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if (arr[i] < pivot)       { [arr[i],  arr[lt]] = [arr[lt], arr[i]]; lt++; i++; }
        else if (arr[i] > pivot)  { [arr[i],  arr[gt]] = [arr[gt], arr[i]]; gt--; }
        else                       i++;
    }
    quicksort3(arr, lo, lt - 1);
    quicksort3(arr, gt + 1, hi);
    return arr;
}

// 5) Complexity
// Average:  O(n log n)
// Worst:    O(n²)  (sorted input + naive pivot — fix with randomisation or median-of-three)
// Best:     O(n log n)
// Space:    O(log n) recursion stack (in-place)
// Stable:   NO — equal elements may reorder
// Adaptive: Slightly (three-way partition helps duplicates)

// 6) Iterative version (avoid stack overflow on huge inputs)
function quicksortIterative(arr) {
    const stack = [[0, arr.length - 1]];
    while (stack.length) {
        const [lo, hi] = stack.pop();
        if (lo >= hi) continue;
        const p = partitionLomuto(arr, lo, hi);
        stack.push([lo, p - 1]);
        stack.push([p + 1, hi]);
    }
    return arr;
}

// 7) Real-world: hybrid algorithms
// Production stdlibs use:
//   • Introsort = quicksort + heapsort fallback when recursion deepens (C++ std::sort)
//   • Pattern-defeating quicksort (pdqsort) — adapts to common patterns (Rust slice::sort_unstable)
//   • Dual-pivot quicksort (Java Arrays.sort for primitives)
//   • TimSort = merge sort + insertion sort for small runs (Python, Java for objects, JS Array.prototype.sort)
//
// Switch to insertion sort for small subarrays (< 16 elements) — cache-friendly + fewer swaps.

function quicksortHybrid(arr, lo = 0, hi = arr.length - 1) {
    if (hi - lo < 16) { insertionSort(arr, lo, hi); return arr; }
    const p = partitionLomuto(arr, lo, hi);
    quicksortHybrid(arr, lo, p - 1);
    quicksortHybrid(arr, p + 1, hi);
    return arr;
}

function insertionSort(arr, lo, hi) {
    for (let i = lo + 1; i <= hi; i++) {
        const x = arr[i];
        let j = i - 1;
        while (j >= lo && arr[j] > x) { arr[j + 1] = arr[j]; j--; }
        arr[j + 1] = x;
    }
}

// 8) Stable sort? Choose merge sort instead
// Quicksort isn't stable. If stability matters, use merge sort (or TimSort).
// In JavaScript, Array.prototype.sort() is stable since ES2019 — implemented as TimSort in V8.

// 9) Quickselect — Hoare's selection algorithm; find K-th smallest in O(n) average
function quickselect(arr, k, lo = 0, hi = arr.length - 1) {
    if (lo === hi) return arr[lo];
    const p = partitionLomuto(arr, lo, hi);
    if (k === p)      return arr[p];
    if (k < p)        return quickselect(arr, k, lo, p - 1);
    return quickselect(arr, k, p + 1, hi);
}

quickselect([3, 1, 4, 1, 5, 9, 2, 6, 5], 4);    // 4 (5th smallest, 0-indexed)

// 10) Parallel quicksort
// Each side of the partition is independent → fork two workers / threads.
// Diminishing returns past sqrt(p) threads due to coordination overhead.

// 11) Memory access patterns
// • Quicksort has excellent cache locality (in-place, contiguous access)
// • Beats heapsort + merge sort by 2-3× on cached arrays
// • For very large arrays that exceed RAM, switch to external merge sort

// 12) Benchmarking idea
const n = 1_000_000;
const arr = Array.from({ length: n }, () => Math.random());

const arr1 = [...arr]; const t1 = performance.now(); arr1.sort((a,b)=>a-b);
console.log('Array.sort:', performance.now() - t1);

const arr2 = [...arr]; const t2 = performance.now(); quicksort(arr2);
console.log('quicksort:', performance.now() - t2);

// 13) Common bugs
// • Last-element pivot on sorted input → O(n²); use random or median-of-three
// • Off-by-one in partition bounds — test on size 0, 1, 2, 3, n
// • Stack overflow on huge inputs — switch to iterative
// • Not handling duplicates — use three-way partition for arrays with many equal elements
// • Modifying the comparator inside the partition — must be deterministic
// • Expecting stability — pick merge sort instead
// • Allocating per-call buffer — keep buffer at top-level for hybrid algorithms
// • Treating Hoare partition return value the same as Lomuto's — different recursion bounds!

function quickSort(a, lo = 0, hi = a.length - 1) {
    if (lo >= hi) return a;
    const pivot = a[(lo + hi) >> 1];
    let i = lo, j = hi;
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) { [a[i], a[j]] = [a[j], a[i]]; i++; j--; }
    }
    quickSort(a, lo, j); quickSort(a, i, hi);
    return a;
}