AlgoScope

Quick Sort vs Merge Sort

SortingAlgorithmintermediate

Quick Sort and Merge Sort are both sorting. Play them side by side below, then see exactly where they diverge.

Either player can stop before each decision and ask what happens next: turn on Predict mode in its top bar.

Quick Sort

Full topic

Pick a pivot, push everything smaller left, and the pivot is home for good.

Partitioning indices 0 to 6. The pivot is 7 at index 6. The boundary i starts at index 0.range 0-650114223843576ipivot
Work on indices 0 to 6. Take the last value, 7, as the pivot.

CHOOSE PIVOT -> PARTITION (smaller left, larger right) -> pivot lands in its final place -> RECURSE.

Merge Sort

Full topic

Merge two sorted runs by always taking the smaller front value.

Merging the run at indices 0 to 0 with the run at indices 1 to 1. The smaller of the two front values is written first.merging 0-15011422384357667write
Copy out 5 and 1, then write them back in order, smaller front value first.

MERGE neighbouring runs -> the smaller head is written down -> runs double in width each pass.

How they differ

Both split the array and sort the parts. They do the real work at opposite ends. Quick sort works before it recurses, partitioning around a pivot, so it sorts in place with O(log n) of recursion but falls to O(n^2) when the pivots split badly. Merge sort works after, merging two sorted halves, so it is O(n log n) in every case and stable, at the price of O(n) extra space.

The run shown here takes 29 steps for Quick Sort and 36 steps for Merge Sort. That count moves with the input - use the example tabs above either player to see it change.

What each operation costs, for Quick Sort and Merge Sort side by side.
CostQuick SortMerge Sort
bestO(n log n)O(n log n)
averageO(n log n)O(n log n)
worstO(n^2)O(n log n)
spaceO(log n)O(n)
Documented properties of Quick Sort and Merge Sort.
PropertyQuick SortMerge Sort
comparison based✓✓
stable×✓
in place✓×
adaptive××
online××