Time Complexity comparison of Sorting Algorithms
| Algorithm | Data Structure | Time Complexity | ||
|---|---|---|---|---|
| Best | Average | Worst | ||
| Quicksort | Array | O(n log(n)) |
O(n log(n)) |
O(n^2) |
| Mergesort | Array | O(n log(n)) |
O(n log(n)) |
O(n log(n)) |
| Heapsort | Array | O(n log(n)) |
O(n log(n)) |
O(n log(n)) |
| Bubble Sort | Array | O(n) |
O(n^2) |
O(n^2) |
| Insertion Sort | Array | O(n) |
O(n^2) |
O(n^2) |
| Select Sort | Array | O(n^2) |
O(n^2) |
O(n^2) |
| Bucket Sort | Array | O(n+k) |
O(n+k) |
O(n^2) |
| Radix Sort | Array | O(nk) |
O(nk) |
O(nk) |
Space Complexity comparison of Sorting Algorithms
| Algorithm | Data Structure | Worst Case Auxiliary Space Complexity | ||
|---|---|---|---|---|
| Quicksort | Array | O(n) |
||
| Mergesort | Array | O(n) |
||
| Heapsort | Array | O(1) |
||
| Bubble Sort | Array | O(1) |
||
| Insertion Sort | Array | O(1) |
||
| Select Sort | Array | O(1) |
||
| Bucket Sort | Array | O(nk) |
||
| Radix Sort | Array | O(n+k) |
||