juniorSorting

How does quicksort work and what is its time complexity?

Updated Feb 20, 2026

Short answer

Quicksort picks a pivot, partitions the array so smaller elements sit left and larger sit right, then recurses on both sides. Average time is O(n log n) and it sorts in place with O(log n) stack space. Its weakness is the worst case: a consistently bad pivot gives O(n²), which is why real implementations randomise the pivot or fall back to heapsort.

Deep explanation

Python
def quicksort(arr, lo=0, hi=None):
    hi = len(arr) - 1 if hi is None else hi
    if lo >= hi:
        return
    p = partition(arr, lo, hi)
    quicksort(arr, lo, p - 1)
    quicksort(arr, p + 1, hi)


def partition(arr, lo, hi):          # Lomuto scheme
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1                      # the pivot's final resting position

The key insight is that after partitioning, the pivot is already in its final position — so it is excluded from both recursive calls. That is what guarantees termination.

Complexity. A balanced split halves the problem each time, giving recursion depth log n with O(n) partitioning work per level: O(n log n). A maximally unbalanced split — pivot always the smallest or largest — gives depth n and O(n²). With a fixed last-element pivot, that worst case is triggered by already sorted input, which is depressingly common in practice.

TimeSpace
Best / averageO(n log n)O(log n) stack
WorstO(n²)O(n) stack

Why it is still the default. Despite the worse worst case, quicksort usually beats mergesort in wall-clock time: it sorts in place with excellent cache locality, whereas mergesort allocates O(n) auxiliary space and copies. Production implementations mitigate the worst case with randomised or median-of-three pivots, and introsort switches to heapsort once recursion depth exceeds 2 log n — guaranteeing O(n log n) while keeping quicksort's speed.

Quicksort is not stable: partitioning swaps distant elements, so equal keys can be reordered.

Real-world example

Sorting 10,000,000 order records by timestamp. The naive pivot choice is a trap:

Python
pivot = arr[hi]        # if the data arrives already sorted -> O(n²)

Order exports usually are roughly time-ordered, so this hits the worst case on real data. Randomising removes the dependency on input order:

Python
import random
def partition(arr, lo, hi):
    r = random.randint(lo, hi)
    arr[r], arr[hi] = arr[hi], arr[r]     # random pivot to the end, then as before
    ...

Now no particular input reliably triggers O(n²) — an adversary would have to guess the random seed.

Common mistakes

  • - Choosing a fixed first or last element as pivot, which makes already-sorted input the worst case — the most common real-world input shape.
  • - Including the pivot in a recursive call, which prevents the problem shrinking and loops forever.
  • - Claiming quicksort is stable
  • partitioning swaps non-adjacent elements and reorders equal keys.
  • - Ignoring the O(n) worst-case stack depth
  • recursing on the smaller partition first bounds it at O(log n).
  • - Using plain quicksort on adversarial or untrusted input without randomisation, which is exploitable as a denial-of-service vector.

Follow-up questions

  • How does quicksort compare with mergesort?
  • What is introsort?
  • How do you handle arrays with many duplicate keys?
  • Why does recursing on the smaller partition first bound stack depth?

More Sorting interview questions

View all →