Sorting Algorithm Comparison
Comprehensive comparison of all featured sorting algorithms
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity | Stable | In-Place | Method | Use Cases |
|---|---|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes | Exchanging | Educational, Small datasets |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes | Selection | Educational, Small datasets |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes | Insertion | Small datasets, Nearly sorted data |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No | Merging | Large datasets, Linked lists |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes | Partitioning | Large datasets, Arrays |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes | Selection | Large datasets, Guaranteed performance |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes | No | Distribution | Small range integers |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes | No | Distribution | Integers, Strings |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No | Hybrid | Python's default sort |
| Gnome Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes | Insertion | Educational |
| Cocktail Shaker Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes | Exchanging | Educational, Bidirectional bubble sort |
| Shell Sort | O(n log n) | O(n^(4/3)) | O(n²) | O(1) | No | Yes | Insertion | Medium-sized datasets |
| Comb Sort | O(n log n) | O(n²/2^p) | O(n²) | O(1) | No | Yes | Exchanging | Improved bubble sort |
| Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | Yes | No | Distribution | Uniformly distributed data |
| Bogo Sort | O(n × n!) | O((n+1)×n!) | O(∞) | O(1) | No | Yes | Random | Educational (worst-case example) |
Understanding the Table
Time Complexity
- O(1) - Constant time
- O(n) - Linear time
- O(n log n) - Linearithmic time
- O(n²) - Quadratic time
- O(n!) - Factorial time (very slow)
Space Complexity
- O(1) - Constant space (in-place)
- O(log n) - Logarithmic space
- O(n) - Linear space
- O(n + k) - Linear space plus extra for counting/buckets
Stability
Stable algorithms maintain the relative order of equal elements
In-Place vs Not In-Place
- In-Place: Uses only O(1) extra space
- Not In-Place: Requires additional space proportional to input size
When to Use Each Algorithm
For Small Datasets
Use Insertion Sort or Bubble Sort for very small arrays (n ≤ 20) where simplicity matters more than performance.
For Large Datasets
Use Quick Sort or Merge Sort for large arrays where O(n log n) performance is crucial.
For Nearly Sorted Data
Insertion Sort or Bubble Sort perform very well on data that's already mostly sorted.
When Stability Matters
Choose Merge Sort, Timsort, or Insertion Sort when you need to maintain the relative order of equal elements.
For Guaranteed Performance
Heap Sort or Merge Sort provide consistent O(n log n) performance in worst case.
For Integers with Small Range
Counting Sort or Radix Sort can achieve linear time complexity.