How do you implement quick sort, and when does it become slow?
Pick a pivot, partition so smaller elements go left and larger go right, then recursively sort both sides. It averages O(n log n) but becomes O(n squared) when the pivot is always the smallest or largest element.
Explain it simply
Imagine sorting exam papers by marks. Pick one paper as the pivot. Everyone with fewer marks goes to the left pile, everyone with more goes to the right. The pivot is now in its final place. Repeat on each pile.
If you always pick the lowest paper as pivot, the left pile is empty and the right pile has everything else, so each step removes only one paper. That is the O(n squared) case, and it happens on already sorted data if you pick the first element.
Example
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
const pivot = arr[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[hi]] = [arr[hi], arr[i]];
quickSort(arr, lo, i - 1);
quickSort(arr, i + 1, hi);
return arr;
}
console.log(quickSort([10, 7, 8, 9, 1, 5])); // Output: [1,5,7,8,9,10]Complexity
Average O(n log n), worst O(n squared); space O(log n) average for the stack.
What to say in the interview
"I pick a pivot, partition the array so smaller values come first, put the pivot in its final slot, and recurse on both sides. Average time is O(n log n) with O(log n) stack space. Worst case is O(n squared) with a bad pivot, which I avoid with a random or median-of-three pivot."
Common mistakes
- Always choosing the first or last element on sorted input.
- Off-by-one errors on the recursive ranges: the pivot index itself is excluded.