About QuickSort
QuickSort selects a pivot element, partitions the array so all elements less than the pivot come before it and all greater come after, then recursively sorts the sub-arrays. Average-case O(n log n) but worst-case O(n²) when the pivot is poorly chosen.
Complexity Analysis
- Time Complexity
- O(n log n)
- Space Complexity
- O(log n)
- Difficulty
- intermediate
Key Concepts
Divide and Conquer
QuickSort divides the problem by partitioning around a pivot, conquers by recursively sorting sub-arrays, and combines trivially (the array is sorted in-place).
Lomuto Partition
The Lomuto scheme picks the last element as pivot and maintains a boundary i: everything at or before i is ≤ pivot. Simple to implement but O(n²) on already-sorted input.
In-Place Sorting
QuickSort sorts in-place using O(log n) stack space for recursion. No auxiliary array is needed (unlike Merge Sort).
Not Stable
QuickSort is not stable — the partition step can change the relative order of equal elements.
Common Pitfalls
Worst-case O(n²)
With Lomuto partition and already-sorted input, each partition removes only one element, leading to O(n²). Randomized pivot or median-of-three avoids this in practice.
Off-by-one in partition
The boundary i starts at low - 1 (NOT low). The pivot swap goes to i + 1 (NOT i). Getting these wrong corrupts the invariant.