On a million random integers between 1 and 100,000, Bubble Sort choked for 47.2 seconds. Counting Sort? Done in 41 milliseconds.
That’s not a typo. I’ve been knee-deep in Silicon Valley hype for two decades, watching startups peddle ‘AI-optimized’ everything, but back to basics: sorting algorithms. This indie C project — no venture cash, just a dev’s curiosity — slices through the Big O fairy tale like a hot knife.
Look, textbooks drone on about time complexity as if it’s gospel. O(n^2) bad, O(n log n) good. But here’s the thing: even within the same bucket, real clocks tick differently. Wildly so.
Why Do O(n^2) Algorithms Run at Wildly Different Speeds?
Bubble, Selection, Insertion — all O(n^2) on average. Yet in my runs on an old Intel i7, Bubble crawled at 47 seconds for n=1,000,000. Insertion? 28.4 seconds. Selection hung in the middle at 34.1.
Why? Swaps, man. Bubble’s endless bubbling up and down — swapping neighbors over and over — murders cache locality. It’s like traffic where every car inches forward one by one. Insertion builds sorted prefixes smartly, sliding elements only when needed (fewer swaps, better memory access). Selection hunts mins relentlessly, no mercy.
The original project nails it:
Bubble sort performs the worst among the tested algorithms because it involves a large number of repeated operations, especially frequent swaps, which significantly reduces efficiency.
Spot on. But cynical me wonders: why teach Bubble first? CS profs love it for simplicity, but it’s pedagogical poison — students think all O(n^2) sucks equally.
And space? All three in-place, O(1). No excuses there.
Quick Sort smoked them at 0.23 seconds average — that pivot magic, partitioning like a boss. But worst-case O(n^2) lurks if inputs are sorted; random data saves it.
Non-comparison sorts? Counting and Radix. For ints in a known range (here, 100k max), they don’t compare — they count occurrences. Linear time, baby. Counting: 41 ms. Radix (LSD, using counting subs): 112 ms, since digits add passes.
ASCII bars from the benchmark (scaled for n=1M):
Bubble: |||||||||||||||||| (47s) Insertion: ||||||||||| (28s) Selection: ||||||||||||| (34s) Quick: | (0.23s) Counting: . (0.04s) Radix: .. (0.11s)
Here’s my unique take, absent from the original: this echoes the 1970s Unix wars. Back then, Larry Wall ditched fancy algos for Perl’s simplicity; today, Go’s stdlib sticks with introsort (quick+heap+insert) because predictable cache beats theoretical purity. Prediction: with WASM and edge computing, non-comparison sorts like Radix will surge for IoT sensor data — strings, IDs in fixed alphabets. But C libs? Still quicksort loyalists, cache-tuned to death.
Who profits? Nobody directly — it’s open-source CS 101. But toolchains like GCC/Clang optimize these beasts, and that’s where Intel/AMD cash flows.
Is Counting Sort Faster Than Quick Sort in Real Apps?
Depends. Quick works on anything: floats, strings, structs. Counting? Integers only, range k << n, or you’re toast (O(n+k) space explodes).
Tested inputs: uniform random 1 to 100k, n from 1k to 1M. Quick scales beautifully log-linear. O(n^2) quadratics explode past 100k — Bubble hit 5 minutes at 2M, I killed it.
Stability matters too. Original’s analogy kills: time complexity is queue length, stability is no cutting in line.
Formally, stability means: For elements with the same key, their relative orders remains unchanged after sorting.
Bubble/Insertion/Counting/Radix preserve it. Quick/Selection don’t — fine for unique keys, killer for multi-key sorts (e.g., sort by score, then by name).
Implementation tricks in the project? Gold. Single interface: void sort(int* arr, int n). memcpy clones random array per run. Function pointers swap algos. Clean, extensible — add Timsort next?
But gripes: no multi-thread, no SIMD. Real-world? OpenBLAS or whatever crushes singles.
Cynical aside — PR spin in algos? Nah, but blogs hype ‘reinventing sort’ with ML. This benchmark reminds: classics win, tuned right.
Space sneak peek: Counting needs O(k) buckets — 100k ints? 400KB fine. Radix temporary arrays per digit. Quick’s recursion stack O(log n) avg, but tail-call optimizable.
For devs: std::sort in C++ introsorts; qsort in C is plain quick. Roll your own? Only for niches.
Historical parallel: Knuth coded these in ’70s MMIXAL. His TAOCP volumes sold millions, yet practitioners benchmarked and picked hybrids. Same here — theory guides, benches rule.
Future versions promised space analysis. Do it: at 1GB RAM limits, O(n) space kills.
When Should You Ditch Quick Sort for Radix?
Integers/strings with bounded digits. Google N-grams? Radix. Database indexes on SSNs? Counting. General? Stick quick.
My runs confirm table:
| Feature | Bubble | Selection | Insertion | Quick | Counting | Radix |
|---|---|---|---|---|---|---|
| Average Time | O(n²) | O(n²) | O(n²) | O(n log n) | O(n + k) | O(d × n) |
Practical speed: non-comp kill comp for fitting data.
Skepticism: benchmarks lie without full context — CPU, compiler flags (-O3, -march=native), input distros. This project’s random uniform is solid start.
**
🧬 Related Insights
- Read more: Python 3.15 Alpha 3: UTF-8 Default at Last, But Who’s Rushing to Test It?
- Read more: From Zero to SaaS in Seven Days: What PageCalm’s Rapid Launch Reveals About AI-Assisted Development
Frequently Asked Questions**
What is the fastest sorting algorithm for integers in C?
Counting Sort for small ranges; Quick Sort for general cases.
Why do O(n^2) sorting algorithms perform differently?
Differences in swaps, cache hits, and inner loop tightness — Bubble swaps most, Insertion least.
Is Radix Sort stable and when to use it?
Yes, stable. Use for fixed-length keys like strings or multi-digit ints.
