Academics · High School · Computer science

Watch a sort
think, one step
at a time.

Type a list and step through four classic sorts and two searches, forward and back, with a sentence for every comparison. Guess the count first, then race all four on the same numbers.

Open the algorithm labWhat you get
4sorting algorithms, stepped one comparison at a time
2searches, linear and binary
66lists checked against a second version

The algorithm lab

Pick a list and an algorithm, then press Step. The arrow keys work on the bars too.

Loading the algorithm lab. If nothing appears, turn on JavaScript.

Four sorts, one idea each

Every sort here does the same job. What differs is the rule for which two values to compare next, and that rule decides how the work grows.

Bubble

Swap neighbors that are out of order

Each pass carries the largest value left to the end. A pass with no swaps means the list is sorted, so a nearly sorted list finishes fast.

for each pass: for each neighbor pair: if left > right: swap
Insertion

Grow a sorted part, one value at a time

Take the next value and shift larger ones right until it fits. This is how most people sort a hand of cards.

for each value after the first: shift larger values right drop the value in the gap
Selection

Find the smallest, put it next

The fewest swaps of the four, at most n − 1, but always the same number of comparisons, however sorted the list already is.

for each position: find the smallest after it swap it into place
Merge

Split in half, sort each half, merge

Merging two sorted runs takes at most one comparison per value placed. For 16 values that caps the work at 49 comparisons, against 120 for the other three.

sort(list): sort(left half) sort(right half) merge the halves

What you get

Academics · High SchoolFree

What you finish with
A clear picture of how bubble, insertion, selection and merge sort and linear and binary search work, step by step on your own numbers, with the comparison counts that show why some are faster. A saved log of your runs and a printed lab report.
Who it is for
High school students in an introductory computer science, AP Computer Science Principles or AP Computer Science A course; teachers who want a live demonstration; anyone learning to code who wants to see what a sort actually does.
Format
Browser lab in four parts: Sort, Search, How fast it grows and My runs. Works on a phone, tablet or computer, by touch or keyboard. Prints a lab report; saves the run log as a .csv.
Access
Free. No account, no sign-in and nothing to install. Everything you type stays in this browser; nothing is sent to Caveat.
Where it lives
The High School space in Caveat Academics.
Support
Questions, a correction or a request: team@caveatacademic.com.
Why the choice matters: at 32 values bubble sort can need 496 comparisons, merge sort 129. The gap widens with every value added.

How to use it

  1. Load the example, or type up to 16 numbers and pick one of the four sorts.
  2. Type a guess for the number of comparisons, then press Step (or the right arrow key on the bars) and read each sentence.
  3. Press Race all four to compare the counts on the same list. Try an already sorted list and a reversed one.
  4. Open Search to see binary search halve a list, and How fast it grows to see what happens at a million values.

Open the algorithm lab

How the counting works

The same steps you watch are the ones that are counted.

Check 1: 15 left, middle is 513910192738435164707782889196Check 2: 7 left, middle is 823910192738435164707782889196Check 3: 3 left, middle is 703910192738435164707782889196Check 4: 1 left, middle is 77, found3910192738435164707782889196Check 1: 15 left, middle is 513910192738435164707782889196Check 2: 7 left, middle is 823910192738435164707782889196Check 3: 3 left, middle is 703910192738435164707782889196Check 4: 1 left, middle is 77, found3910192738435164707782889196
Binary search on the 15-value example list, looking for 77. Each check rules out half of what is left: 15 values, then 7, then 3, then 1.

How the lab counts

A comparison is any time two values from the list are compared, or, in a search, any value checked against the one you are looking for. A move is a swap in bubble and selection sort, a shift or the final drop in insertion sort, and a copy back into the list in merge sort, so moves are counted the way each algorithm actually spends them.

Bubble sort here stops after a pass with no swaps; insertion sort stops each scan at the first value that is not larger; merge sort splits with the smaller half on the left and sends ties to the left run, which keeps equal values in their original order. Textbooks vary on these details, so a count can differ by a few from another book’s version of the same algorithm.

Checked a second way

Every count on the page comes from the same steps you watch. Before the page was built, the four sorts and two searches were written again in Python with the same rules and run on 66 lists and 41 searches; the page’s counts are compared with those on every test run.

Sources

  1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 4th edition (MIT Press, 2022): insertion sort (chapter 2), merge sort and its running time (chapter 2), and the analysis of comparisons.
  2. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition (Addison-Wesley, 1998), section 5.2.4 (merge sort uses at most n⌈lg n⌉ − 2^⌈lg n⌉ + 1 comparisons) and section 6.2.1 (binary search needs at most ⌊lg n⌋ + 1 comparisons).
  3. Computer Science Teachers Association, K–12 Computer Science Standards (2017), 3B-AP-10 (use and adapt classic algorithms) and 3B-AP-11 (evaluate algorithms in terms of their efficiency, correctness and clarity).
  4. College Board, AP Computer Science Principles Course and Exam Description (2020), learning objectives AAP-2.P (binary search) and AAP-4.A (algorithmic efficiency).

The timing column assumes 100 million comparisons a second to make the sizes comparable; real speed depends on the computer, the language and the data. Example lists are made up. Support: team@caveatacademic.com.