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

[7, 2, 9, 5, 1, 8] pivot = 5
smaller: [2, 1] pivot: 5 larger: [7, 9, 8]
sort each side recursively → [1,2] 5 [7,8,9]

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 stable

Common 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.

More General articles