Last month, I went down a rabbit hole: I implemented six classic sorting algorithms from scratch in pure Python (Bubble, Selection, Insertion, Merge, Quick, Heap) and benchmarked them properly on CPython.
I expected the usual Big-O story. What I got was a reality check: Python’s interpreter overhead changes everything.
Textbooks say Quick/Merge/Heap are fast. In Python? They’re okay… but sorted() (Timsort) beats them by 5–150×. Here’s why — and when you should never write your own sort.
The Surprise Results (Real Benchmarks)
I tested on random, nearly-sorted, reversed, and duplicate-heavy data using timeit with warm-ups, median timing, and GC controls.
| Algorithm | 100 elements | 1,000 elements | 5,000 elements | Practical Limit |
|---|---|---|---|---|
| Bubble Sort | 0.001s | 0.15s | 3.2s | ~500 elements |
| Selection Sort | 0.001s | 0.13s | 2.8s | ~500 elements |
| Insertion Sort | 0.0005s | 0.08s | 1.9s | ~1,000 (great on nearly-sorted!) |
| Merge Sort | 0.002s | 0.025s | 0.14s | Usable but slow |
| Quick Sort | 0.002s | 0.021s | 0.11s | Usable but recursion hurts |
| Heap Sort | 0.002s | 0.029s | 0.16s | Reliable but never wins |
| sorted() | 0.0003s | 0.0045s | 0.025s | Use this always |
Key shocks:
- Insertion sort beats Merge/Quick on <100 elements (low overhead wins).
- Bubble sort dies at ~1,000 elements due to expensive comparisons.
- Timsort (built-in) exploits real-world patterns and runs in C — untouchable.
Why Hand-Written Sorts Lose in Python
-
Comparisons are expensive:
a > b→ method dispatch, type checks (not one CPU instruction). - Recursion overhead: Quick sort’s function calls are costly.
- Memory allocations: Merge sort creates thousands of temporary lists → GC pauses.
- Timsort is a hybrid genius: Detects runs, uses insertion sort for small chunks, merges adaptively — all in optimized C.
Example: Insertion sort (often the small-data winner):
def insertion_sort(arr):
arr = arr.copy()
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
The Verdict
Never implement your own sort in production Python.
Use sorted() or .sort() — they’re faster, stable, and battle-tested.
Do it only for learning purposes or rare edge cases.
Want the full deep dive?
- Detailed explanations
- All source code
- Benchmark script
- Raw benchmark data
👉 Read the complete post on my blog:
https://emitechlogic.com/sorting-algorithm-in-python/
Run the benchmarks yourself
-
GitHub Repository:
https://github.com/Emmimal/python-sorting-benchmarks
What surprised you most about Python’s sorting performance?
Drop a comment — curious to hear your take.
