⚡ Sorting Algorithm Complexity 📖

⚡ Sorting Algorithm Complexity

#	Algorithm	⏱️ Best	⚖️ Average	🔻 Worst	💾 Space	⚙️ Stability
1	⚡ Quick Sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	❌ No
2	🧩 Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	✅ Yes
3	🚀 Timsort	$O(n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	✅ Yes
4	⛰️ Heap Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	❌ No
5	💧 Bubble Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✅ Yes
6	✍️ Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✅ Yes
7	🪞 Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	❌ No
8	🌲 Tree Sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(n)$	❌ No
9	🐚 Shell Sort	$O(n \log n)$*	~$O(n^{1.3})$	$O(n^2)$	$O(1)$	❌ No
10	🪣 Bucket Sort	$O(n + k)$	$O(n + k)$	$O(n^2)$	$O(n + k)$	✅ Yes**
11	🔢 Radix Sort	$O(nk)$	$O(nk)$	$O(nk)$	$O(n + k)$	✅ Yes
12	🧮 Counting Sort	$O(n + k)$	$O(n + k)$	$O(n + k)$	$O(k)$	✅ Yes

Notes

• k = range of keys (Counting/Bucket Sort) or number of digits (Radix Sort).
• *Shell Sort's complexity depends on the gap sequence; there is no universally accepted average-case complexity.
• Bucket Sort is stable only if the sorting algorithm used within each bucket is stable (e.g., Insertion Sort).

---

Related Posts

• 🧱 Data Structures & Big O Complexity — the Big O/Big Omega/Big Theta notation used throughout this comparison
• 🔎 Searching Algorithm Complexity — Binary Search and other sorted-data-dependent searches this sorting step enables