This blog is a snapshot of all well known sorting algorithms and its attributes.
| Algorithm | Time complexity | Space complexity | Attributes | ||
|---|---|---|---|---|---|
| Best case | Average case | Worst case | |||
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Stable, In-Place, Comparison based, used as base case for hybrid sort (timsort) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Not Stable, In-Place, Comparison based, used in heavy memory write use cases , used in small dataset |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Stable, In-Place, Comparison based |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable, Not In-Place, Comparison based, large dataset, external sorting (files, directories) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) (average) O(n) (worst) | Not Stable, In-Place, Comparison based, general purpose |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Not Stable, In-Place, Comparison based, when guaranteed to be O(n log n) and constant space requirement |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Stable, Not In-Place, Not Comparison based, Integer with small know range (score, age) |
| Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | Depends on hash function(Stable or not), Not In-Place, Not Comparison based, Uniformly distributed floating point numbers |
| Radix Sort | O(d · (n + k)) | O(d · (n + k)) | O(d · (n + k)) | O(n + k) | Stable, Not In-Place, Not Comparison based, Integer with small know range (id, phone number) |