Time Complexity comparison of Sorting Algorithms


 

Algorithm Time Complexity
  Best Average Worst
Quick Sort O(n log(n)) O(n log(n)) O(n^2)
Mergesort O(n log(n)) O(n log(n)) O(n log(n))
Heapsort O(n log(n)) O(n log(n)) O(n log(n))
Bubble Sort O(n) O(n^2) O(n^2)
Insertion Sort O(n) O(n^2) O(n^2)
Select Sort O(n^2) O(n^2) O(n^2)
Bucket Sort O(n+k) O(n+k) O(n^2)
Radix Sort O(nk) O(nk) O(nk)

 


Radix Sort Algorithm

Running Time:

O(np) , p:number of passes of sorting algorithm, n: number of elements