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
Each bar represents one element. Colors identify compared elements, the pivot or key, the final region and the active range.
Use 2 to 16 values. This visualizer accepts values from 0 to 999.
- 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.