the last question
Sorting Olympics
Mar 5, 2025
I implemented 48 sorting algorithms and made them fight each other in a tournament bracket. Because I wanted to know which ones actually work in practice, not just in theory. So I wrote this.
The computer science textbooks lie to you. They tell you merge sort is O(n log n) and that’s supposed to mean something. But when you actually run the code, sometimes bubble sort beats it on small lists, and quicksort can lose to block sort. The real world doesn’t care about big-O; it cares about cache, constants, and quirks.
There are too many sorting libraries. I could have stopped. I did not. It started as an excuse to learn weird sorts and quietly became a toolkit and a tournament. Fine.
How many ways can you sort a list? More than I liked.
Basic: bubble, selection, insertion, merge, quick, heap.
Advanced: shell, tim, intro, library, block, smooth.
Specialized: pancake, patience, tournament, cycle, gnome, cocktail, etc.
Linear, Non-comparison, and Theoretical: All the weird ones they don’t teach in school.
I implemented 48 algorithms. Some of them are absurd.
Visualization
Watching O(n²) in slow motion is satisfying. I admit that and move on.
Benchmarking
I wanted to know which sorts were fast, which were slow, and which were catastrophically bad. I also wanted proof that bogosort really does suck.
Tournaments
Algorithms compete in a single-elimination deathmatch. Losers get quietly recorded. Winners get a line in the README.
Sometimes the results surprised me. Most times they did not.
(base) engelbart@Utkarshs-MacBook-Pro sort_olympics % SIZE=100 TIMEOUT=5 python run.py
==================================================
SORT OLYMPICS
==================================================
CONFIGURATION:
Timeout: 5s
Tournament size: 100 elements
Data type: random
Value range: 0 to 1000
Visualization: Disabled
ALGORITHMS:
Fundamental: 6
Advanced: 6
Specialized: 14
Linear-time: 6
Noncomparison: 5
Theoretical: 11
Total: 48
VERIFYING ALGORITHMS... ✅ 48/48
==================================================
TOURNAMENT BEGINS! (48 competitors)
==================================================
ROUND 1 (64 competitors)
Bogosort defeats Slowsort (43.72x faster)
Patience Sort defeats Cycle Sort (1.59x faster)
Radix Sort Lsd defeats Bead Sort (290.14x faster)
Msd Radix Sort Inplace defeats Tournament Sort (1.79x faster)
Block Sort defeats Quick Sort (1.29x faster)
Spreadsort defeats Odd Even Sort (1.54x faster)
Bucket Sort Uniform defeats Cocktail Sort (1.37x faster)
Intro Sort defeats Comb Sort (1.47x faster)
I Cant Believe It Can Sort defeats Bucket Sort Integer (2.80x faster)
Exchange Sort defeats Postman Sort (3.17x faster)
Merge Insertion Sort defeats Radix Sort Msd (11.83x faster)
Bubble Sort defeats Pancake Sort (1.28x faster)
Franceschini Mergesort defeats Tree Sort (1.47x faster)
Recombinant Sort defeats Sorting Network (17.06x faster)
Insertion Sort defeats Strand Sort (1.34x faster)
Shell Sort defeats Merge Sort (2.39x faster)
Gnome Sort defeats Stooge Sort (40.58x faster)
Library Sort defeats Burstsort (24.00x faster)
Tim Sort defeats Smooth Sort (1.29x faster)
Cube Sort defeats Spaghetti Sort (6.85x faster)
Pigeonhole Sort defeats Counting Sort (3.04x faster)
Inplace Merge Sort defeats Bitonic Sort (1.87x faster)
Heap Sort defeats Thorup Sort (21.48x faster)
Selection Sort defeats Flashsort (4.04x faster)
ROUND 2 (32 competitors)
Patience Sort defeats Bogosort (17.82x faster)
Radix Sort Lsd defeats Msd Radix Sort Inplace (1.10x faster)
Block Sort defeats Spreadsort (3.11x faster)
Intro Sort defeats Bucket Sort Uniform (3.60x faster)
Exchange Sort defeats I Cant Believe It Can Sort (1.82x faster)
Merge Insertion Sort defeats Bubble Sort (4.28x faster)
Recombinant Sort defeats Franceschini Mergesort (3.41x faster)
Shell Sort defeats Insertion Sort (2.18x faster)
Library Sort defeats Gnome Sort (6.32x faster)
Tim Sort defeats Cube Sort (5.29x faster)
Inplace Merge Sort defeats Pigeonhole Sort (1.19x faster)
Heap Sort defeats Selection Sort (2.05x faster)
ROUND 3 (16 competitors)
Radix Sort Lsd defeats Patience Sort (1.74x faster)
Intro Sort defeats Block Sort (1.19x faster)
Merge Insertion Sort defeats Exchange Sort (4.15x faster)
Shell Sort defeats Recombinant Sort (1.03x faster)
Tim Sort defeats Library Sort (1.33x faster)
Heap Sort defeats Inplace Merge Sort (5.34x faster)
ROUND 4 (8 competitors)
Intro Sort defeats Radix Sort Lsd (3.29x faster)
Shell Sort defeats Merge Insertion Sort (1.63x faster)
Tim Sort defeats Heap Sort (1.40x faster)
ROUND 5 (4 competitors)
Shell Sort defeats Intro Sort (1.33x faster)
Tim Sort advances (opponent: BYE)
ROUND 6 (2 competitors)
Shell Sort defeats Tim Sort (1.48x faster)
THIRD PLACE MATCH
Intro Sort defeats Tim Sort (1.26x faster)
==================================================
TOURNAMENT RESULT
==================================================
CHAMPION: 🏆 Shell Sort (Advanced)
RUNNER-UP: 🥈 Tim Sort (Advanced)
Shell Sort 🏆 [0.000029s]
Tim Sort 🥈 [0.000043s]
│5
│├─ Shell Sort [0.000028s]
│└─ Intro Sort [0.000037s]
│ │4
│ │├─ Intro Sort [0.000038s]
│ │└─ Radix Sort Lsd [0.000124s]
│ │ │3
│ │ │├─ Radix Sort Lsd [0.000126s]
│ │ │└─ Patience Sort [0.000219s]
│ │ │ │2
│ │ │ │├─ Patience Sort [0.000217s]
│ │ │ │└─ Bogosort [0.003866s]
│ │ │ │ │1
│ │ │ │ │├─ Bogosort [0.004436s]
│ │ │ │ │└─ Slowsort [0.193950s]
│ │ │ │ │1
│ │ │ │ │├─ Patience Sort [0.000268s]
│ │ │ │ └─ Cycle Sort [0.000427s]
│ │ │ │2
│ │ │ │├─ Radix Sort Lsd [0.000124s]
│ │ │ └─ Msd Radix Sort Inplace [0.000137s]
│ │ │ │1
│ │ │ │├─ Radix Sort Lsd [0.000122s]
│ │ │ │└─ Bead Sort [0.035349s]
│ │ │ │1
│ │ │ │├─ Msd Radix Sort Inplace [0.000153s]
│ │ │ └─ Tournament Sort [0.000273s]
│ │ │3
│ │ │├─ Intro Sort [0.000039s]
│ │ └─ Block Sort [0.000046s]
│ │ │2
│ │ │├─ Block Sort [0.000047s]
│ │ │└─ Spreadsort [0.000147s]
│ │ │ │1
│ │ │ │├─ Block Sort [0.000050s]
│ │ │ │└─ Quick Sort [0.000064s]
│ │ │ │1
│ │ │ │├─ Spreadsort [0.000143s]
│ │ │ └─ Odd Even Sort [0.000220s]
│ │ │2
│ │ │├─ Intro Sort [0.000041s]
│ │ └─ Bucket Sort Uniform [0.000148s]
│ │ │1
│ │ │├─ Bucket Sort Uniform [0.000154s]
│ │ │└─ Cocktail Sort [0.000211s]
│ │ │1
│ │ │├─ Intro Sort [0.000043s]
│ │ └─ Comb Sort [0.000063s]
│ │4
│ │├─ Shell Sort [0.000027s]
│ └─ Merge Insertion Sort [0.000044s]
│ │3
│ │├─ Merge Insertion Sort [0.000042s]
│ │└─ Exchange Sort [0.000174s]
│ │ │2
│ │ │├─ Exchange Sort [0.000145s]
│ │ │└─ I Cant Believe It Can Sort [0.000265s]
│ │ │ │1
│ │ │ │├─ I Cant Believe It Can Sort [0.000285s]
│ │ │ │└─ Bucket Sort Integer [0.000799s]
│ │ │ │1
│ │ │ │├─ Exchange Sort [0.000147s]
│ │ │ └─ Postman Sort [0.000467s]
│ │ │2
│ │ │├─ Merge Insertion Sort [0.000044s]
│ │ └─ Bubble Sort [0.000188s]
│ │ │1
│ │ │├─ Merge Insertion Sort [0.000045s]
│ │ │└─ Radix Sort Msd [0.000533s]
│ │ │1
│ │ │├─ Bubble Sort [0.000188s]
│ │ └─ Pancake Sort [0.000241s]
│ │3
│ │├─ Shell Sort [0.000028s]
│ └─ Recombinant Sort [0.000029s]
│ │2
│ │├─ Recombinant Sort [0.000028s]
│ │└─ Franceschini Mergesort [0.000095s]
│ │ │1
│ │ │├─ Franceschini Mergesort [0.000112s]
│ │ │└─ Tree Sort [0.000165s]
│ │ │1
│ │ │├─ Recombinant Sort [0.000043s]
│ │ └─ Sorting Network [0.000736s]
│ │2
│ │├─ Shell Sort [0.000028s]
│ └─ Insertion Sort [0.000061s]
│ │1
│ │├─ Insertion Sort [0.000065s]
│ │└─ Strand Sort [0.000087s]
│ │1
│ │├─ Shell Sort [0.000040s]
│ └─ Merge Sort [0.000096s]
│5
│├─ Tim Sort
└─ BYE
│4
│├─ Tim Sort [0.000042s]
└─ Heap Sort [0.000059s]
│3
│├─ Tim Sort [0.000047s]
│└─ Library Sort [0.000063s]
│ │2
│ │├─ Library Sort [0.000058s]
│ │└─ Gnome Sort [0.000366s]
│ │ │1
│ │ │├─ Gnome Sort [0.000344s]
│ │ │└─ Stooge Sort [0.013960s]
│ │ │1
│ │ │├─ Library Sort [0.000076s]
│ │ └─ Burstsort [0.001825s]
│ │2
│ │├─ Tim Sort [0.000052s]
│ └─ Cube Sort [0.000275s]
│ │1
│ │├─ Tim Sort [0.000055s]
│ │└─ Smooth Sort [0.000071s]
│ │1
│ │├─ Cube Sort [0.000246s]
│ └─ Spaghetti Sort [0.001686s]
│3
│├─ Heap Sort [0.000057s]
└─ Inplace Merge Sort [0.000303s]
│2
│├─ Inplace Merge Sort [0.000300s]
│└─ Pigeonhole Sort [0.000358s]
│ │1
│ │├─ Pigeonhole Sort [0.000432s]
│ │└─ Counting Sort [0.001315s]
│ │1
│ │├─ Inplace Merge Sort [0.000366s]
│ └─ Bitonic Sort [0.000683s]
│2
│├─ Heap Sort [0.000057s]
└─ Selection Sort [0.000117s]
│1
│├─ Heap Sort [0.000081s]
│└─ Thorup Sort [0.001746s]
│1
│├─ Selection Sort [0.000149s]
└─ Flashsort [0.000602s]
Results
Bogosort did not win. Predictable.
Shell sort won. It’s 65 years old and still better than most at this tiny problem size. I file that away.
Lesson: context matters. Shell sort isn’t asymptotically optimal, but it has low overhead and tight loops: advantages that matter at 100 elements. Spreadsort can utterly crush slowsort in one matchup and then lose to a merge variant the next. Changing constraints rearranges everything.
==================================================
RESULTS BY CATEGORY
==================================================
FUNDAMENTAL ALGORITHMS:
1st: Heap Sort - 3 wins, 0.000063s avg time
2nd: Insertion Sort - 1 wins, 0.000063s avg time
3rd: Selection Sort - 1 wins, 0.000133s avg time
ADVANCED ALGORITHMS:
1st: Shell Sort - 6 wins, 0.000030s avg time
2nd: Intro Sort - 5 wins, 0.000039s avg time
3rd: Tim Sort - 4 wins, 0.000047s avg time
SPECIALIZED ALGORITHMS:
1st: Recombinant Sort - 2 wins, 0.000033s avg time
2nd: Exchange Sort - 2 wins, 0.000155s avg time
3rd: Patience Sort - 2 wins, 0.000235s avg time
LINEAR ALGORITHMS:
1st: Radix Sort Lsd - 3 wins, 0.000124s avg time
2nd: Bucket Sort Uniform - 1 wins, 0.000151s avg time
3rd: Pigeonhole Sort - 1 wins, 0.000395s avg time
NONCOMPARISON ALGORITHMS:
1st: Msd Radix Sort Inplace - 1 wins, 0.000145s avg time
2nd: Spreadsort - 1 wins, 0.000145s avg time
3rd: Postman Sort - 0 wins, 0.000467s avg time
THEORETICAL ALGORITHMS:
1st: Merge Insertion Sort - 3 wins, 0.000044s avg time
2nd: Franceschini Mergesort - 1 wins, 0.000104s avg time
3rd: I Cant Believe It Can Sort - 1 wins, 0.000275s avg time
==================================================
NOTABLE MATCHES
==================================================
Radix Sort Lsd vs Bead Sort - 290.14x speed difference
Bogosort vs Slowsort - 43.72x speed difference
Gnome Sort vs Stooge Sort - 40.58x speed difference
==================================================
SUMMARY
==================================================
+----------------------------+---------------+------+--------+--------------+
| Algorithm | Category | Wins | Losses | Avg Time (s) |
+----------------------------+---------------+------+--------+--------------+
| 🏆 Shell Sort | Advanced | 6 | 0 | 0.000030 |
| Intro Sort | Advanced | 5 | 1 | 0.000039 |
| 🥈 Tim Sort | Advanced | 4 | 2 | 0.000047 |
| Merge Insertion Sort | Theoretical | 3 | 1 | 0.000044 |
| Heap Sort | Fundamental | 3 | 1 | 0.000063 |
| Radix Sort Lsd | Linear | 3 | 1 | 0.000124 |
| Recombinant Sort | Specialized | 2 | 1 | 0.000033 |
| Block Sort | Advanced | 2 | 1 | 0.000048 |
| Library Sort | Advanced | 2 | 1 | 0.000066 |
| Exchange Sort | Specialized | 2 | 1 | 0.000155 |
| Patience Sort | Specialized | 2 | 1 | 0.000235 |
| Inplace Merge Sort | Specialized | 2 | 1 | 0.000323 |
| Insertion Sort | Fundamental | 1 | 1 | 0.000063 |
| Franceschini Mergesort | Theoretical | 1 | 1 | 0.000104 |
| Selection Sort | Fundamental | 1 | 1 | 0.000133 |
| Msd Radix Sort Inplace | Noncomparison | 1 | 1 | 0.000145 |
| Spreadsort | Noncomparison | 1 | 1 | 0.000145 |
| Bucket Sort Uniform | Linear | 1 | 1 | 0.000151 |
| Bubble Sort | Fundamental | 1 | 1 | 0.000188 |
| Cube Sort | Specialized | 1 | 1 | 0.000260 |
| I Cant Believe It Can Sort | Theoretical | 1 | 1 | 0.000275 |
| Gnome Sort | Specialized | 1 | 1 | 0.000355 |
| Pigeonhole Sort | Linear | 1 | 1 | 0.000395 |
| Bogosort | Theoretical | 1 | 1 | 0.004151 |
| Comb Sort | Specialized | 0 | 1 | 0.000063 |
| Quick Sort | Fundamental | 0 | 1 | 0.000064 |
| Smooth Sort | Advanced | 0 | 1 | 0.000071 |
| Strand Sort | Specialized | 0 | 1 | 0.000087 |
| Merge Sort | Fundamental | 0 | 1 | 0.000096 |
| Tree Sort | Specialized | 0 | 1 | 0.000165 |
| Cocktail Sort | Specialized | 0 | 1 | 0.000211 |
| Odd Even Sort | Specialized | 0 | 1 | 0.000220 |
| Pancake Sort | Specialized | 0 | 1 | 0.000241 |
| Tournament Sort | Specialized | 0 | 1 | 0.000273 |
| Cycle Sort | Specialized | 0 | 1 | 0.000427 |
| Postman Sort | Noncomparison | 0 | 1 | 0.000467 |
| Radix Sort Msd | Linear | 0 | 1 | 0.000533 |
| Flashsort | Noncomparison | 0 | 1 | 0.000602 |
| Bitonic Sort | Theoretical | 0 | 1 | 0.000683 |
| Sorting Network | Theoretical | 0 | 1 | 0.000736 |
| Bucket Sort Integer | Linear | 0 | 1 | 0.000799 |
| Counting Sort | Linear | 0 | 1 | 0.001315 |
| Spaghetti Sort | Theoretical | 0 | 1 | 0.001686 |
| Thorup Sort | Theoretical | 0 | 1 | 0.001746 |
| Burstsort | Noncomparison | 0 | 1 | 0.001825 |
| Stooge Sort | Theoretical | 0 | 1 | 0.013960 |
| Bead Sort | Theoretical | 0 | 1 | 0.035349 |
| Slowsort | Theoretical | 0 | 1 | 0.193950 |
+----------------------------+---------------+------+--------+--------------+
-
Tiny lists favor dumb algorithms. At 100 elements insertion sort beats quick, heap, and sometimes merge. The constant factor wins; predictable loops are friends with the CPU.
-
Shell sort is a sprinter. It wins small brackets and disappears as the input grows and cache misses accumulate. Asymptotics stop mattering when overhead dominates.
-
Linear time is not a magic bullet. Counting/radix/bucket lose on small inputs because setup costs dominate. At 10,000 elements the linear contenders do better, but it’s not always dramatic.
-
Domain size decides things. My data lived in [0, 1000]. That helps pigeonhole and bucket and rearranges the podium. Change the domain, change the winners.
-
Tree sort over-performed. Balanced BST inserts looked worse on paper than they behaved here.
-
Thorup sort can behave like its papers claim. On larger inputs it competes with linear buckets. Noted.
What actually matters
Constant factors beat asymptotics on realistic inputs. Shell sort won because it minimizes overhead: tight loops, decent locality, no extra allocations. The fancy stuff spent cycles on bookkeeping and lost time.
The tournament confirmed a few things I half-suspected:
-
Theoretical curiosities rarely win. Bead sort, spaghetti sort, bogosort: they’re thought experiments, not tools. Slowsort being ~1090× slower than spreadsort is confirmation, not shock.
-
Linear time still has overhead. Counting and radix lost early because building buckets dominates on small arrays.
-
Simple algorithms are resilient. Insertion sort behaved like the human algorithm it is and beat several complex contenders.
Most algorithms solve different problems: quicksort for average case, heapsort for worst-case guarantees, counting for integers, radix for fixed-width keys. Bogosort exists to make one doubt their life choices.
The interesting ones are pragmatic: shell sort, smoothsort, they assume patterns in data and exploit them. They’re not pretty; they’re useful.
Building this forced me to think about edge cases: expensive comparisons, limited memory, structured data. Each algorithm encodes an answer to a constraint.
Also: visualization and benchmarks taught me more than the tournament bracket. Watching bubble sort flail is educational. Timsort’s adaptivity explains why standard libraries picked it.
Why?
I have no good reason. But now if someone asks which sort is fastest, I can just point at the tournament tree.
Useful? Not really. Standard library sorts are fine. Still, seeing alternatives makes the choice less mysterious.
Forty-eight algorithms is probably overkill. I don’t regret it.
Don’t treat theory as gospel. Write code, measure, and let the data (and your laziness) decide.