The Sorting Race: Why Speed Matters
About this lesson, for parents and teachers
Two algorithms get the exact same shuffled list and the exact same speed. One finishes while the other is still crawling. Can you work out why, and how much worse it gets as the list grows?
Ages 12–14 · about 8 minutes · builds on Sorting Animals by Swapping
Try this
- Press Race. Watch the purple bars: those are the two items being compared right now.
- Read the comparison counters. Merge sort and bubble sort sorted the same list, so the only difference is the algorithm.
- Slide n up to 48 or 64 and race again. Your results appear as dots on the Work vs n chart.
- Answer the question: if n doubles, how much more work does bubble sort do?
How it works
To compare algorithms fairly, engineers count the basic steps they take instead of timing them on one computer. For sorting, the basic step is a comparison: is this item bigger than that one? In this race both algorithms do exactly one comparison per tick, so whoever needs fewer comparisons wins.
Bubble sort walks through the list comparing neighbours and swapping them when they are in the wrong order. Each pass bubbles the biggest remaining item to the end. With n items it does up to (n-1) + (n-2) + ... + 1 comparisons, which adds up to n(n-1)/2. For 64 items that is 2,016 comparisons.
Merge sort splits the list in half, sorts each half (by splitting again, all the way down to single items), then merges sorted halves by repeatedly taking the smaller front item. There are about log2(n) levels of splitting, and merging each level costs at most n comparisons, so the total is roughly n log2(n). For 64 items that is under 384.
Big O notation describes how work grows with n, ignoring small details. Bubble sort is O(n²): double the list and the work goes up about four times. Merge sort is O(n log n): double the list and the work only slightly more than doubles. At a million items, that gap is the difference between a blink and many hours.
Where engineers use this
The sort functions built into Python, JavaScript and Java use merge-sort-style algorithms (Timsort and its relatives) because O(n log n) keeps working when apps sort millions of rows.
Words to know
- Comparison
- Checking which of two items is bigger. It is the basic step we count when measuring a sorting algorithm.
- Big O notation
- A way to describe how an algorithm's work grows as the input size n grows, such as O(n²) or O(n log n).
- Bubble sort
- A simple sort that repeatedly swaps neighbours that are out of order. Easy to write, slow on big lists.
- Merge sort
- A divide-and-conquer sort that splits the list, sorts each half, then merges the sorted halves.
Talk about it
Goal: Race bubble sort against merge sort and see why some algorithms scale and others crawl.
- Why is it fairer to count comparisons than to time the program with a stopwatch?
- If one algorithm takes 4 times longer every time the list doubles, how long would a list 8 times bigger take?
- Where in daily life do you sort things, and which method do you use?
Without a screen: Shuffle 16 playing cards. One person sorts by bubble sort (only compare and swap neighbours), another by merge sort (split into piles of one, then merge pairs of sorted piles). A third person tallies every comparison each sorter makes, then compare the tallies.
Curriculum links: CSTA K-12 2-AP-13 (decompose problems), 3A-AP-15 (justify algorithm choice by efficiency), AP Computer Science Principles Big Idea 3 (algorithmic efficiency)
Questions
What is Big O notation in simple terms?
Big O tells you how the amount of work an algorithm does grows as the input gets bigger. O(n²) means doubling the input roughly quadruples the work, while O(n log n) means doubling the input only a little more than doubles it.
Why is merge sort faster than bubble sort?
Bubble sort compares almost every pair of items, about n²/2 comparisons. Merge sort splits the list in half again and again and only compares items while merging, which takes about n log2(n) comparisons. On 64 items that is around 2,000 versus under 400.
Is bubble sort ever used in real code?
Rarely. It is a great teaching tool because it is easy to understand, and it can be fine for tiny or nearly sorted lists, but real libraries use faster algorithms like Timsort, merge sort or quicksort.