Balanced partitions create log n levels with Θ(n) work each, Θ(n log n).
Sorting algorithms · 3/7
Quicksort
Places each pivot and recurses on both partitions.
Average timeΘ(n log n)
SpaceΘ(log n) average
StableNo
In placeYes
How it works
This visualization uses Lomuto partitioning with the last value as pivot.
Invariant: A[low…i−1] ≤ pivot and A[i…j−1] > pivot; A[j] is classified next.
Step-by-step visualization
The bar view shows comparisons and swaps; the parallel tree follows the subarrays produced by each partition and the final positions of the pivots.
Use 2 to 16 values. This visualizer accepts values from 0 to 999.
Partition tree
Blue: current subarray · yellow: pivot · green: final position
- Comparisons
- 0
- Writes
- 0
- Swaps
- 0
- Pass / level
- 0
active
comparison
pivot / key
final
Pseudocode linked to the visualization
quickSort(A, low, high)if low ≥ high: returnpivot ← A[high]i ← lowfor j ← low to high − 1if A[j] ≤ pivot: swap A[i], A[j]; i++swap A[i], A[high]quickSort(A, low, i − 1); quickSort(A, i + 1, high)
The highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.
Complexity analysis
With randomized pivots, expected depth is Θ(log n) and time Θ(n log n).
Repeated 0 and n−1 splits yield T(n)=T(n−1)+Θ(n)=Θ(n²).
Partitioning is in-array; the stack is Θ(log n) average and Θ(n) worst. It is unstable.
Properties at a glance
Stability concerns the relative order of elements with equal keys.
This classification refers to the version shown on this page.
When to use it and what to avoid
A good choice when…
Very fast for in-memory arrays due to locality and small constants.
Common mistake
A fixed end pivot without countermeasures is risky on ordered or adversarial input.