Divide & conquer · Intermediate
Quick Sort
Choose a pivot, partition values around it, then sort the two sides.
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n²)
- Space
- O(log n) avg.; O(n) worst
- Stability
- Not stable
- Memory model
- In-place
How it builds order
- Choose a pivot.
- Scan the range and grow the lower-than-pivot region.
- Place the pivot between the two partitions.
- Recursively sort each side.
Why it works
Partitioning gives the pivot its final rank; recursion repeats the same argument on smaller independent ranges.
Watch for: After partitioning, the pivot is final even though both sides still need work.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.