Quick Sort

sorting · O(n log n) avg

5

Configure inputs and press Visualize to begin.

64
34
25
12
22
11
90
45
Default
Comparing
Swap
Pivot
Sorted
Found
Pseudocode & Implementations
3 approaches

Pivot = last element. Partition with one pointer. Simple but O(n²) on sorted input.

QUICKSORT(A, lo, hi):
  IF lo < hi:
    p = PARTITION(A, lo, hi)
    QUICKSORT(A, lo, p-1)
    QUICKSORT(A, p+1, hi)

PARTITION(A, lo, hi):   // Lomuto
  pivot = A[hi]
  i = lo - 1
  FOR j = lo TO hi-1:
    IF A[j] <= pivot:
      i++
      SWAP(A[i], A[j])
  SWAP(A[i+1], A[hi])
  RETURN i+1
Complexity Analysis

Time Complexity

Best Case
LinearithmicO(n log n)
Average
LinearithmicO(n log n)
Worst Case
QuadraticO(n²)
Space (aux)
LogarithmicO(log n)
UnstableIn-placedivide-conquercache-friendlypractical
About

Selects a pivot, partitions the array around it, then recursively sorts both partitions. Cache-friendly and fast in practice.

Key Insight

Despite O(n²) worst case, excellent average performance due to cache efficiency. Most real-world implementations use randomized pivot.

Use Cases

General-purpose sortingArraysWhen average performance matters