Skip to content
← Back to algorithms

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How this algorithm works

How it works

  1. Choose the last element of the current range as the pivot.
  2. Walk through the range, comparing each element to the pivot.
  3. Whenever an element is smaller than the pivot, swap it into the growing 'less-than-pivot' region.
  4. After the scan, swap the pivot into place right after that region — it is now in its final sorted position.
  5. Recursively apply the same process to the sub-array left of the pivot.
  6. Recursively apply the same process to the sub-array right of the pivot.

Key concepts

  • Divide-and-conquer
  • Not stable (the partition step can reorder equal elements)
  • In-place (partitions within the original array, O(log n) recursion stack)
  • Average-case O(n log n) but O(n^2) worst case on already-sorted input with this pivot choice

When to use it

The default choice for general-purpose in-memory sorting when average-case performance and low memory overhead matter more than worst-case guarantees or stability. Widely used in standard library sort implementations (often combined with other algorithms as a hybrid).

Did you know

Quick sort's worst case (O(n^2)) happens on already-sorted or reverse-sorted input when the pivot is always the last element — which is why production implementations often randomize the pivot or use median-of-three selection.