Time Complexity Overview
Time complexity is a critical concept when evaluating the performance of sorting algorithms. It measures the amount of time an algorithm takes to run as a function of the length of the input list. Here’s an overview of time complexity in some common sorting algorithms, particularly in Python:
| Algorithm | Best | Average | Worst | Memory | Stable | Methods |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Comparison-based, Exchange |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No | Comparison-based, Selection |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Comparison-based, Insertion |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Divide and Conquer, Merging |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No | Divide and Conquer, Partition |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Comparison-based, Heap |
| Shell Sort | O(n log n) | O(n(log n)^2) | O(n(log n)^2) | O(1) | No | Comparison-based, Insertion |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes | Non-comparison, Distribution |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes | Non-comparison, Counting |
| Bucket Sort | O(n + k) | O(n + k) | O(n^2) | O(n) | Yes | Non-comparison, Distribution |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Hybrid (Merge + Insertion) |
| Comb Sort | O(n^2 / 2^p) | O(n^2 / 2^p) | O(n^2) | O(1) | No | Comparison-based, Exchange |
| Pigeonhole Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes | Non-comparison, Distribution |
| Cycle Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No | Comparison-based, In-place |
| Cocktail Shaker Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Comparison-based, Exchange |
| Gnome Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Comparison-based, Insertion |
| Odd-Even Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Comparison-based, Parallel |
| Bitonic Sort | O(log^2 n) | O(log^2 n) | O(log^2 n) | O(n log^2 n) | Yes | Comparison-based, Parallel |
| Bogo Sort | O(n) | O((n+1)!) | O((n+1)!) | O(1) | No | Random-based, Brute-force |
| Stooge Sort | O(n^(log 3/log 1.5)) | O(n^(log 3/log 1.5)) | O(n^(log 3/log 1.5)) | O(n) | No | Comparison-based, Recursive |
