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