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) |