Sorting

Bubble sort versus merge sort

An interactive lesson with 8 steps, about 7 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Bubble sort compares neighbours: about $\tfrac12 n^2$ comparisons.
• Merge sort divides and conquers: about $n\log_2 n$.
• For big inputs, the algorithm matters far more than the computer’s speed.

Steps

1. Bubble sort
2. Merge sort
3. Merge sort in action
4. Merge sort, step by step
5. Merging
6. A million items
7. Nearly sorted
8. The speed limit