Sorting — Putting Things in Order
PlayHow computers compare and rearrange data, step by step
This concept builds on Binary Numbers — How Computers Count. Consider exploring it first for the best experience.
The Problem
Each bar on the canvas is one number in random order, and the tallest bar is the largest. Every algorithm below gets the bars into ascending order, but they spend very different numbers of comparisons doing it. Watch the "Comparisons" card count them, and the green bars mark positions that are finally in place.
Bubble Sort
Click 'Bubble' to run it. The two yellow bars are the neighbours being compared; if the left one is taller, they swap. Each pass carries the tallest unsorted bar to the right end, where it turns green. The "Pass" card counts passes. Bubble sort makes up to about n²/2 comparisons, stopping early only when a pass needs no swaps.
Selection Sort
Click 'Selection' to run it. The orange bar is the smallest value found so far in the unsorted part, and the yellow bar is the one being checked against it. At the end of each pass the orange bar swaps to the front and turns green. It always makes exactly n(n−1)/2 comparisons but very few swaps.
Insertion Sort
Click 'Insertion' to run it. The bars on the left stay sorted; each new bar slides left past every taller neighbour until it reaches its place, so you see the sorted run grow one bar at a time. The worst case is still about n²/2 comparisons, but nearly sorted input finishes in close to n.
Merge Sort
Click 'Merge' to run it. The blue shaded band marks the two sorted halves being merged: the smaller front bar of each half is written back first, so the band leaves sorted. Halving the array gives about log₂ n levels of merging, each costing about n comparisons, for roughly n log₂ n in total.
Quick Sort
Click 'Quick' to run it. The rightmost bar of the current range is the pivot; each yellow comparison checks one bar against it, and smaller bars swap toward the left end of the range. The pivot then drops into its final slot and turns green. With lucky pivots that is about n log₂ n comparisons, but already sorted input degrades to n².
Worked Example: n = 10⁶
When a run finishes, the chart compares all five algorithms on the same array. Drag the 'Array size' slider to 30: 'Selection' makes 435 comparisons (30 × 29 ÷ 2) while 'Merge' makes roughly 110. Scale to n = 10⁶: n² = 10¹², but n log₂ n ≈ 10⁶ × 20 = 2 × 10⁷, so the ratio is about 50 000× fewer comparisons.
How It Works — Step by Step
-
1
The Problem
Each bar on the canvas is one number in random order, and the tallest bar is the largest. Every algorithm below gets the bars into ascending order, but they spend very different numbers of comparisons doing it. Watch the "Comparisons" card count them, and the green bars mark positions that are finally in place.
-
2
Bubble Sort
Click 'Bubble' to run it. The two yellow bars are the neighbours being compared; if the left one is taller, they swap. Each pass carries the tallest unsorted bar to the right end, where it turns green. The "Pass" card counts passes. Bubble sort makes up to about n²/2 comparisons, stopping early only when a pass needs no swaps.
-
3
Selection Sort
Click 'Selection' to run it. The orange bar is the smallest value found so far in the unsorted part, and the yellow bar is the one being checked against it. At the end of each pass the orange bar swaps to the front and turns green. It always makes exactly n(n−1)/2 comparisons but very few swaps.
-
4
Insertion Sort
Click 'Insertion' to run it. The bars on the left stay sorted; each new bar slides left past every taller neighbour until it reaches its place, so you see the sorted run grow one bar at a time. The worst case is still about n²/2 comparisons, but nearly sorted input finishes in close to n.
-
5
Merge Sort
Click 'Merge' to run it. The blue shaded band marks the two sorted halves being merged: the smaller front bar of each half is written back first, so the band leaves sorted. Halving the array gives about log₂ n levels of merging, each costing about n comparisons, for roughly n log₂ n in total.
-
6
Quick Sort
Click 'Quick' to run it. The rightmost bar of the current range is the pivot; each yellow comparison checks one bar against it, and smaller bars swap toward the left end of the range. The pivot then drops into its final slot and turns green. With lucky pivots that is about n log₂ n comparisons, but already sorted input degrades to n².
-
7
Worked Example: n = 10⁶
When a run finishes, the chart compares all five algorithms on the same array. Drag the 'Array size' slider to 30: 'Selection' makes 435 comparisons (30 × 29 ÷ 2) while 'Merge' makes roughly 110. Scale to n = 10⁶: n² = 10¹², but n log₂ n ≈ 10⁶ × 20 = 2 × 10⁷, so the ratio is about 50 000× fewer comparisons.
Key Takeaways
O(n²) vs O(n log n)
Bubble, selection, and insertion sort need roughly n² comparisons. Merge sort and quicksort need only about n log n — a dramatic improvement for large datasets. Change the array size and compare the chart after each run to see the gap grow.
In-Place vs Extra Memory
Bubble, selection, insertion sort, and quicksort rearrange the original array in place. Merge sort needs extra space proportional to n to hold the merged result.
Stability
A stable sort preserves the original order of equal elements. Merge sort, bubble sort, and insertion sort are stable; selection sort and quicksort (as commonly implemented) are not. Stability matters when sorting records by multiple keys.
Connected Concepts
Binary Numbers
Every comparison between two numbers compares their binary representations.
Recursion
Merge sort and quicksort both split and recurse on subarrays — classic divide-and-conquer algorithms.
Big-O Notation
The n² versus n log n gap in the comparison chart is exactly what Big-O notation describes.
Binary Search
Sorting pays off later: once data is in order, binary search finds any item in about log₂ n steps.
Heaps
A heap gives heapsort, another n log n algorithm that sorts in place without the worst case of quicksort.
Updated
- — Added a predict question on selection sort at 14 vs 28 bars, and a goal: sort 28 bars with a faster algorithm.
- — Steps now follow the algorithm you pick, with a worked comparison-count example
- — Corrected the speed-up figure (about 50,000×, not 400×) and synced step highlights with the running algorithm