Quick Sort chooses a pivot, partitions the array around it, and recursively sorts each side.

Imagine organizing a deck of cards: pick one card as a divider, place every smaller card to its left and every larger card to its right, then repeat on each side.

In practice it is the fastest general-purpose sort for in-memory data — it works in place with excellent cache locality. It powers the default sort in most standard libraries (usually as Introsort, a quicksort variant).

How It Works

1. Choose a pivot element (the visualizer uses the last element of the current range).
2. Partition: scan the range, moving every element smaller than the pivot to the left and every larger element to the right.
3. Place the pivot in its final sorted position between the two partitions.
4. Recursively apply Quick Sort to the left and right sub-arrays.
5. Stop when a range has zero or one element.

Key Insight

After partitioning, the pivot is guaranteed to be in its final position — nothing on its left belongs on its right, and vice versa. The efficiency story is about balance:

• Balanced pivots — near the middle, each level touches n elements across log n levels → O(n log n).
• Extreme pivots — e.g., already-sorted data with a last-element pivot → lopsided splits, n levels → O(n²).

That is why real implementations randomize the pivot or use median-of-three, and why Introsort switches to heap sort when recursion depth grows too large.

Worked Example

Sort [5, 3, 8, 1, 2] with last-element pivot:

• Range [5, 3, 8, 1, 2], pivot = 2: partition walks and swaps → [1, 2, 3, 8, 5], pivot 2 lands at index 1.
• Left [1]: done. Right [3, 8, 5], pivot = 5: partition → [3, 5, 8], pivot 5 lands at index 1.
• Left [3]: done. Right [8]: done.

Result: [1, 2, 3, 5, 8]. In the visualizer, the pivot is highlighted while the partition scan colors smaller elements as it swaps them left.

Edge Cases & Pitfalls

• Already sorted input — with a last-element pivot, this is the worst case (O(n²)): every split is maximally lopsided. Random pivot or median-of-three fixes this.
• All identical values — with the naive last-element (Lomuto) partition, every element equals the pivot, so the pivot always lands at the far end and each split is n−1/0 — the worst case again (O(n²)), and a naive implementation may loop.
• Duplicates — Quick Sort is unstable: long-distance swaps can reorder equal values.
• Recursion depth — the call stack is O(log n) average but O(n) worst. Deep recursion on adversarial input can overflow; Introsort guards against this.
• Tiny sub-ranges — slower than insertion sort below ~10 elements; that is why Introsort delegates them.

Comparison With Other Sorts

Applications

• Default in-memory sort in C, Java (Arrays.sort), Rust, and Go (as Introsort)
• Partition-based selection — finding the k-th smallest element (Quickselect) is the same partition trick without sorting both sides
• Sorting arrays where cache locality gives a huge constant-factor win over other O(n log n) sorts

Practice Trajectory

1. Hand-trace the partition of [9, 2, 7, 1, 5] with pivot 5, writing the array after each swap.
2. Construct an input that forces the worst case with a last-element pivot, and explain the recursion depth.
3. Implement Lomuto partition, then convert it to a randomized-pivot version.
4. Explain why quicksort’s worst case is unlikely with random pivots.
5. Trace Quickselect to find the 3rd smallest in [7, 10, 4, 3, 20, 15].