Chapters 3–7 · Brute Force · Decrease-, Divide- and Transform-and-Conquer · Space-Time Tradeoffs

Sorting Studio

Ten ways to sort one array, from selection sort to Least Significant Digit (LSD) radix sort. Watch every key comparison, swap and write as it happens, or race up to four algorithms on the same input and see which one does the least work.

Algorithm Partition Pivot

Pick 2 to 4 racers. All of them sort the same input.

Your array (whole numbers 0–999, up to 32)

Size n = 10

Key comparisons

How to read this

Bars: Each bar is one array element; its height is its value and the small number under it is its index. Colors follow the legend: yellow = being compared, blue = current/active, red = just swapped or written, purple = pivot, green = in its final place, grey = out of play.
Shaded band: Quicksort and mergesort work on a sub-range A[l..r]; the orange band marks it.
Mergesort rows: Row d holds the pieces at recursion depth d. Going down the rows is splitting; coming back up is merging. Green outline = sorted run, orange = being built.
Heap tree: The tree and the array are the same data: the children of index k are 2k + 1 and 2k + 2. Nodes that turn green have left the heap and are final.
Count / D / S rows and buckets: The counting sorts and the bucket-based sorts use extra arrays; those rows are that extra memory, and the "extra cells" counter measures it.
Counters: Key comparisons is the basic operation Levitin counts for comparison sorts. Swaps / moves counts data movement. Extra cells is the peak number of extra array cells. Recursion depth is how deep the call stack got.
Badges: Stable: equal keys keep their original order. In place: only a constant amount of extra memory (plus, for quicksort, the recursion stack).

Try this

Same count, any input. Run selection sort on Sorted, then Reversed, with n = 10. Both make exactly n(n−1)/2 = 45 comparisons. Bubble sort with early exit drops to n − 1 = 9 on sorted input.
Quicksort's bad day. Pick quicksort (Hoare, first-element pivot) and load Sorted with n = 16. Every split is lopsided and the recursion depth reaches about n. Switch the pivot to median of three and watch the depth and comparisons fall.
Stability you can see. Load 5, 3, 5, 1, 3 into mergesort and watch the tie rule "B[i] ≤ C[j], take B" keep equal keys in order. Then try comparison counting sort: as written, it places equal keys in reverse order.
Race. Race selection, insertion, mergesort and quicksort on Nearly sorted with n = 32. Insertion sort should win comparisons; on Random, mergesort or quicksort wins. Why does the ranking flip?
Zero comparisons. Race distribution counting sort against mergesort on Few unique. Distribution counting makes 0 key comparisons, so what does it pay instead? (Check its extra-cells counter in single mode.)

How to read this

Try this

Go deeper