Sorting Algorithms
Watch nine sorting algorithms sort a row of bars and count every comparison and move, on five kinds of input or on bars drawn by hand.
- Compared
- Moved
- Partitioning value
- Sorted
Each bar is a value. The algorithm compares two values (amber) and moves them (red) until the bars rise from left to right, and every count is exact. Drag across the bars to draw an input by hand; Rerun sorts it again, and a new Algorithm sorts the same bars.
How is Sorting Algorithms working for you?
About Sorting Algorithms
- Algorithms
- 9, from bubble sort to Batcher's bitonic network
- Bars
- 8 to 256
- Fewest comparisons on average
- log₂(n factorial), Hoare 1962
- Selection sort
- n(n − 1)/2 comparisons for every input
Sorting Algorithms runs nine sorting algorithms on a row of bars, one value per bar, and replays every comparison and move they make. Each algorithm runs once on a copy of the input and records its events, so the counts beside the bars are the events themselves, exact rather than estimated. A comparison tests two values; a swap moves two values and a write moves one.
The input decides much of the cost. Insertion sort makes one shift for each pair of values out of order, so a nearly sorted row takes few moves and a reversed one n(n − 1)/2. Selection sort compares every pair once, whatever the input. Quicksort, from C. A. R. Hoare's 1962 paper, averages about 2n ln n comparisons when its bound is chosen at random, but with the first element as the bound a sorted row splits off one value at a time. Jon Bentley and Douglas McIlroy's three-way partition (1993) never compares the values equal to the partitioning element again, and Kenneth Batcher's bitonic network (1968) compares the same pairs for every input.
The chart plots the comparisons for 8 to 256 bars with the same settings beside log₂(n factorial), the fewest comparisons any comparison sort can average, and n(n − 1)/2, every pair once. Each sorted run adds a row to the Runs table, so algorithms and inputs can be set side by side. Drag across the bars to draw an input by hand, and export a PNG, video, GIF or CSV.
How to use Sorting Algorithms
- Pick an algorithm and an input. Choose an Algorithm and an Input (Random, Nearly sorted, Reversed, Few unique or Sorted), and set the number of Bars from 8 to 256.
- Press Play. Amber bars are being compared and red bars are being moved; when the row is sorted, every bar turns green. The counter shows the step, the comparisons and the moves so far. At the default Speed a comparison takes 0.1 s.
- Read why. Under the canvas a sentence explains the count, with the exact total where one holds for the bars on screen: n(n − 1)/2 comparisons for selection sort, one move per pair out of order for insertion and bubble sort, the same comparisons for every input in the bitonic network.
- Try a bad pivot. With Quicksort, set Pivot to First element and Input to Sorted: each partition splits off one value and the comparisons grow as n²/2. Random and Median of three avoid it.
- Read the chart. The dots are the comparisons for 8 to 256 bars with the same algorithm, input, pivot and seed, and the circle is this run. The dashed lines mark log₂(n factorial), the fewest comparisons any comparison sort can average, and n(n − 1)/2, every pair once; for the bitonic network a third line gives its exact count.
- Draw an input. Drag across the bars to set their heights. Rerun sorts the drawn bars again from the first step, a new Algorithm or Pivot sorts the same bars by another rule, Restart makes a new input of the chosen kind, and Reset returns every setting to its default.
- Compare runs. Each sorted run adds a row to the Runs table with its comparisons and moves; the table shows the settings that differ between rows. Reset clears it.
- Export. Save a PNG, a video or GIF of the run, or record the full run. The CSV files hold the comparisons and moves after every event, the Runs table and the chart's dots. A share link carries bars drawn by hand.
Frequently asked questions
Which sorting algorithm is fastest?
It depends on the input and on what an operation costs. On random input, quicksort with a random bound averages about 2n ln n, or 1.39 n log₂ n, comparisons (Hoare 1962), within a factor of 1.4 of log₂(n factorial), the fewest any comparison sort can average. Insertion sort needs one comparison and one move per pair out of order: about n²/4 on random input, since each pair is out of order with chance 1/2, but only n − 1 comparisons on sorted input.
What is an inversion?
A pair of values in the wrong order. Insertion sort makes one shift per inversion and bubble sort one swap, so their moves follow the inversions exactly: a sorted row has none and a reversed row of n values has n(n − 1)/2, 276 for 24 bars.
Why does quicksort slow down on sorted input?
Only with a poor bound. If the first element of each segment is the bound, on sorted input it is the segment's smallest value, so each partition splits off a single value and the comparisons grow as n²/2. Hoare (1962) advised choosing the bound at random; the median of the first, middle and last elements, Singleton's rule as Bentley and McIlroy (1993) describe it, also avoids the slow case.
What is a sorting network?
A fixed sequence of compare-exchange steps that sorts every input. Batcher's bitonic network (1968) sorts 2ᵖ values in p(p + 1)/2 rounds of 2ᵖ⁻¹ comparisons each, (n/4) log₂ n (log₂ n + 1) in all, and the comparisons of a round can run at the same time: 240 comparisons for 32 bars.
Are the counts exact?
Yes. Each algorithm runs once and records every comparison, swap and write; the canvas replays the record, so the counters are the events themselves. Comparisons are three-way, as a library sort's comparison function is: one test of two values tells less, equal or greater.
References
- Shell, D. L. (1959). A high-speed sorting procedure. Communications of the ACM 2(7), 30–32.
- Hoare, C. A. R. (1962). Quicksort. The Computer Journal 5(1), 10–16.
- Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM 7(6), 347–348.
- Floyd, R. W. (1964). Algorithm 245: Treesort. Communications of the ACM 7(12), 701.
- Batcher, K. E. (1968). Sorting networks and their applications. AFIPS Spring Joint Computer Conference, 307–314.
- Bentley, J. L., & McIlroy, M. D. (1993). Engineering a sort function. Software: Practice and Experience 23(11), 1249–1265.
- Ciura, M. (2001). Best increments for the average case of Shellsort. Fundamentals of Computation Theory, LNCS 2138, 106–117.





