Sorting Algorithm

Quick Sort

Picks a pivot, partitions the array so everything smaller ends up on its left and everything bigger on its right, then recurses on each side. Its in-place partitioning and excellent cache locality make it the fastest general-purpose sort in practice — despite an O(n²) worst case on adversarial input.

BestO(n log n)
AverageO(n log n)
WorstO(n²)
SpaceO(log n)
StableNo

Try It — Animated Flow

29
8
44
15
3
37
21
Quick sort picks a pivot, partitions everything smaller to its left and bigger to its right, then recurses on each side.
Step 1 / 27
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

Sorting primitive arrays
Java's Arrays.sort(int[]) uses a dual-pivot quicksort — for primitives (no boxing, no stability requirement), quicksort's speed and low memory overhead win out.
In-memory database sorts
Query engines sorting result sets that fit in RAM favor quicksort-family algorithms for their average-case speed and small memory footprint.
General-purpose library sorts
Many C standard library qsort() implementations are quicksort-based, chosen for excellent average-case performance across arbitrary data.
Selecting the k-th smallest value
Quickselect — a one-sided variant of quicksort's partition step — finds the k-th smallest element in average O(n), without sorting the whole array.

Trade-offs

Reach for it when
  • You need the fastest average-case, in-place sort
  • Memory is limited (O(log n) stack space, no extra array)
  • The data isn't adversarially crafted to hit worst case
Avoid it when
  • Worst-case guarantees matter (real-time / safety-critical code — use Heap Sort)
  • Stability is required (use Merge Sort or Tim Sort)
  • Input could be adversarial and pivot choice isn't randomized