Sorting Algorithms: Racing to Order
Watch algorithms compete to sort the fastest
Watch algorithms compete to sort the fastest
Watch three sorting algorithms race side by side. Each bar represents a number. The algorithms rearrange them from shortest to tallest. Click Start to begin.
Press Start to race Bubble Sort vs Selection Sort vs Merge Sort.
Bubble Sort compares each pair of neighbors and swaps them if they are in the wrong order. The largest values "bubble" to the end. Click Step to advance one comparison at a time.
Click Step to compare the highlighted pair. Orange = comparing. Green = sorted.
For small arrays, all algorithms are fast. But as data grows, O(n^2) algorithms become impossibly slow while O(n log n) stays manageable.
Every time you sort a spreadsheet, search results appear, or your music library organizes, a sorting algorithm runs.
Google sorts billions of pages by relevance score. The sort must complete in milliseconds. O(n^2) would take years.
Every ORDER BY clause triggers a sort. Indexes pre-sort data so queries do not have to sort at runtime. This is why indexes make databases fast.
3D games sort triangles by depth (painter's algorithm) or sort transparent objects back to front. 60 times per second.
Tim Peters invented Timsort in 2002 for Python. It exploits the fact that real-world data often has existing order (partially sorted runs). It is now the default sort in Python, Java, and Android.
You've seen how different sorting strategies produce wildly different speeds. Bubble sort is simple but slow. Merge sort is complex but fast. The right algorithm for the job can mean the difference between milliseconds and hours.
Compare neighbors, swap if wrong order, repeat. Easy to understand. But O(n^2) means doubling the data quadruples the time.
Scan for the smallest, put it first, repeat. Always does the same number of comparisons regardless of input. Still O(n^2).
Split in half, sort each half, merge them. O(n log n) means it scales beautifully. Sorting 1 million items takes seconds, not years.
For 10 items, any algorithm is fast. For 10 million, only O(n log n) algorithms finish in reasonable time. Choosing the right algorithm IS programming.
Put your new knowledge into practice!