Quicksort: the idea
Prerequisites: Arrays, recursion, and partitioning around a pivot.
A pivot is an item used to divide a range. This teaching version picks the rightmost item as its pivot. It scans the other items, moving values less than or equal to the pivot into a left region. It then swaps the pivot immediately after that region. The pivot is in its final position, and recursion sorts the left and right ranges.
Try it on the same input
Compare Mixed with Already sorted, Reversed, and All equal. Choosing the last item as pivot can produce severely unbalanced partitions. Watch the active range and recursion depth. Randomized pivots or three-way partitioning address different parts of this problem.
Time, memory, and stability
n is the number of input items. Average O(n log n) over random input permutations with distinct keys; worst O(n²). Average recursion space O(log n), worst O(n). Partitioning itself uses O(1) extra space.
A stable sort preserves the original order of items whose values are equal. This implementation is not stable. Identity labels record each item’s initial position. An unstable algorithm can preserve equal-item order on a particular input; it makes no guarantee for all inputs.
These bounds describe the sorting algorithm itself. The visualization saves a copy of the array at every operation for reversible playback, so recording uses additional time and memory. Its input size is capped at 24 items.
When to use it—and what to watch
This deterministic, two-way partition version exposes bad pivot behavior on purpose. Sorted inputs and many equal keys can cause quadratic work. It does not preserve the order of equal items.
Reading the display
Comparisons count tests between item values. A swap writes two array positions; a merge write updates one. The counters exclude copying merge buffers, index tests, and playback work, so they are teaching measurements rather than elapsed-time benchmarks. Green marks final positions; a highlighted range indicates current work. For recursive algorithms, depth counts the active call levels.
Continue exploring
- Bubble sort — Compare neighbors and let large values travel to the right.
- Selection sort — Find the smallest remaining item and place it in the next slot.
- Insertion sort — Grow a sorted prefix by moving each new item into place.
- Merge sort — Sort two halves, then weave their values into one ordered sequence.