Don't like searching one by one to find the space and time complexities of all sorting algorithms, then here is the Cheatsheet list of Time and Space Complexities of popular Sorting Algorithms like Quicksort, Mergesort, Timsort, Heapsort, Bubble Sort, Insertion Sort, Selection Sort, Tree Sort, Shell Sort, Bucket Sort, Radix Sort, Counting Sort, and Cubesort.
Time Complexities
|
Algorithm |
Best |
Average |
Worst |
|---|---|---|---|
| Quicksort | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
| Mergesort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
| Timsort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
| Heapsort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
| Bubble Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
| Insertion Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
| Selection Sort | Ω(n^2) |
Θ(n^2) |
O(n^2) |
| Tree Sort | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
| Shell Sort | Ω(n log(n)) |
Θ(n(log(n))^2) |
O(n(log(n))^2) |
| Bucket Sort | Ω(n+k) |
Θ(n+k) |
O(n^2) |
| Radix Sort | Ω(nk) |
Θ(nk) |
O(nk) |
| Counting Sort | Ω(n+k) |
Θ(n+k) |
O(n+k) |
| Cubesort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
Space Complexity
|
Algorithm |
Worst |
|---|---|
| Quicksort | O(log(n)) |
| Mergesort | O(n) |
| Timsort | O(n) |
| Heapsort | O(1) |
| Bubble Sort | O(1) |
| Insertion Sort | O(1) |
| Selection Sort | O(1) |
| Tree Sort | O(n) |
| Shell Sort | O(1) |
| Bucket Sort | O(n) |
| Radix Sort | O(n+k) |
| Counting Sort | O(k) |
| Cubesort | O(n) |
