Quicksort Algorithm Explained
Quicksort picks a "pivot" element, partitions the list into elements smaller and larger than the pivot, then recursively sorts each partition.
Published November 15, 2026
Quicksort picks a pivot, partitions the list into items smaller and larger than it, then recursively sorts each part. It averages O(n log n) and is fast in practice, though the worst case is O(n²).
The concept
Choose a pivot (random or median-of-three to avoid bad cases). Put smaller items on the left and larger on the right; the pivot is then in its final place.
It sorts in place with little extra memory, but is not stable and can degrade to O(n²) on already sorted input with a poor pivot rule.
Partition around 5
Practical examples
Clear (not in-place) version
function quick(a) {
if (a.length < 2) return a
const p = a[Math.floor(a.length / 2)]
return [...quick(a.filter(x => x < p)), ...a.filter(x => x === p), ...quick(a.filter(x => x > p))]
}Python
def quick(a):
if len(a) < 2: return a
p = a[len(a)//2]
return quick([x for x in a if x < p]) + [x for x in a if x == p] + quick([x for x in a if x > p])Complexity
average O(n log n) · worst O(n²) · space O(log n) · not stableCommon mistakes
- Always choosing the first element as pivot on sorted data.
- Not handling many duplicates.
- Recursing on the larger partition first (stack depth).
Key takeaways
- Partition around a pivot.
- Average O(n log n).
- Pivot choice matters.
FAQ
Quicksort vs mergesort?
Quicksort is in-place and usually faster; mergesort is stable with guaranteed O(n log n).
What does the built-in sort use?
Usually hybrids like introsort or Timsort.