Reading about a sorting algorithm is one thing. Watching it shuffle a pile of numbers into place, one comparison at a time, is another! This lab lets us run the same numbers through every sorting algorithm we've covered, from the humble Bubble Sort to the hybrid Timsort, and see exactly how much work each one does.
Sort the Numbers
Select the sort you want, and then hit Start Sort below to run the simulation.
Bubble Sort
Read the Bubble Sort tutorial- Best time
- O(n)
- Average time
- O(n²)
- Worst time
- O(n²)
- Extra space
- O(1)
- Stable
- Yes
- Comparisons
- 0
- Swaps
- 0
- Array writes
- 0
- Extra memory writes
- 0
- Extra memory slots
- 0 now / 0 peak
Sort Result
No sort yet. Start Sort will show the counts for this algorithm.
| Algorithm | Comparisons | Swaps | Array writes | Peak extra memory | Steps | Result |
|---|
Running Time and Memory
Here's how each algorithm scales as the number of items, n, grows. For Counting Sort, k is the range of values. For Radix Sort, d is the number of digits and k is the 10 possible digits. Extra space doesn't count the input itself. A stable sort keeps equal values in their original order.
| Algorithm | Best time | Average time | Worst time | Extra space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) to O(n) | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes |
| Radix Sort | O(d · (n + k)) | O(d · (n + k)) | O(d · (n + k)) | O(n + k) | Yes |
| Bogosort | O(n) | O(n · n!) | Unbounded | O(1) | No |
What to Look For
Start with Compare All Nine on the default numbers. The quadratic sorts (Bubble, Selection, and Insertion) make hundreds of comparisons, while Merge Sort, Quicksort, and Timsort need far fewer. Counting Sort and Radix Sort make zero comparisons. They tally values instead, and they pay for that with extra memory.
Now use Customize to load Already sorted numbers. Bubble Sort, Insertion Sort, and Timsort notice the order and finish in a single pass, which is their O(n) best case. Selection Sort and Merge Sort do the same amount of work no matter what. Try Reversed next and watch Timsort flip the whole descending run around with a few swaps.
Keep an eye on Extra memory slots. Bubble, Selection, and Insertion Sort sort in place and never go above zero. Merge Sort needs a buffer as large as the input. Quicksort only needs a small to-do stack of ranges, because this lab always sorts the smaller side first. That keeps the stack at about log2(n) entries even when the pivots are unlucky. Timsort's buffer only needs to hold the smaller-looking left run of each merge.
Load Few unique values to check stability. The letters on matching numbers stay in a, b, c order for the stable sorts. Selection Sort and Quicksort can jumble them.
Finally, give Bogosort a try with five or six numbers, where it usually wins after a few hundred shuffles. With more numbers, the expected number of shuffles explodes (that's the n! in its running time), so the lab politely gives up after 5,000 shuffles instead of freezing your browser.
A few notes on how this lab differs from the tutorials: Merge Sort merges bottom-up instead of recursing, Quicksort uses the tutorial's middle-value partitioning with an explicit stack instead of recursive calls, and Timsort uses a minimum run of 4 to 8 items (real implementations use 32 to 64) and skips galloping mode so every comparison is visible. The results and the running times are the same. For the full stories, follow the tutorial link for any algorithm, or see Meet the Default Sorting Algorithms for what our favorite languages actually use.
Just a final word before we wrap up. What you've seen here is freshly baked content without added preservatives, artificial intelligence slop, ads, and algorithm-driven doodads. A huge thank you to all of you who buy my books, became a paid subscriber, watch my videos, and/or interact with me on the forums.
Your support keeps this site going! 😇
