Quick Sort

Implement quick sort — a classic divide-and-conquer sorting algorithm. You pick one element as the pivot, split the rest of the input into "smaller than pivot" and "greater than pivot," then recursively sort each side and stitch the results back together. Average runtime is O(n log n); with an unlucky pivot it degrades to O(n²). Your job is to get the partition right, handle duplicates and edge cases, and accept a custom comparator.

Signature

// Returns a NEW sorted array. The input must not be mutated.
// `compare(a, b)` returns < 0 if a should come before b, > 0 if after, 0 if equal.
// Default comparator sorts numbers ascending.
function quickSort<T>(
  input: T[],
  compare?: (a: T, b: T) => number
): T[];

Examples

quickSort([3, 7, 1, 4, 8, 2, 5]);
// [1, 2, 3, 4, 5, 7, 8]

// Empty and single-element inputs are returned as a fresh (sorted) copy.
quickSort([]);     // []
quickSort([42]);   // [42]

// Already-sorted input still works — this is the WORST case for a naive
// last-element pivot (degrades to O(n²)) but the output must be correct.
quickSort([1, 2, 3, 4, 5]); // [1, 2, 3, 4, 5]

// Duplicates: every copy survives. No element is dropped or merged.
quickSort([3, 1, 3, 2, 1, 3]); // [1, 1, 2, 3, 3, 3]

// Custom comparator — descending.
quickSort([3, 1, 4, 1, 5], (a, b) => b - a); // [5, 4, 3, 1, 1]

// Custom comparator — by object property.
quickSort(
  [{ age: 30 }, { age: 12 }, { age: 21 }],
  (a, b) => a.age - b.age,
); // [{ age: 12 }, { age: 21 }, { age: 30 }]

Notes

• Return a new array, don't mutate the input. Tests deep-equal the input before and after the call and expect it unchanged. Build the result as you go.
• All-equal arrays must terminate. quickSort([7, 7, 7, 7]) is a real input. A partition that splits into "less than pivot" and "greater than or equal to pivot" will recurse forever on this — handle equals as their own bucket.
• Duplicates are preserved. If 5 appears three times in the input, it appears three times in the output. Stability across equals isn't required, but no element may be silently merged.
• Default comparator is numeric ascending — (a, b) => a - b. Don't fall back to JavaScript's lexicographic default, which sorts [10, 2] as [10, 2].
• Custom comparator must be honoured for every comparison. Hard-coded < / > will fail descending and by-property tests.
• Pure recursion is fine. No call-stack limits are tested — inputs are at most a few thousand elements.
• module.exports = { quickSort } so the test file can require it.