Here is a handy summary table of the time complexity of some popular sorting algorithms, which I culled from Wikipedia.
Algorithm | Stable | Time Complexity | ||
---|---|---|---|---|
Best | Average | Worst | ||
Quicksort | N | Ω(n2) | Θ(n log n) | O(n log n) |
Merge sort | Y | Ω(n log n) (typical) Ω(n) (natural variant) | Θ(n log n) | O(n log n) |
Timsort | Y | Ω(n) | Θ(n log n) | O(n log n) |
Heapsort | N | Ω(n log n) (distinct keys) Ω(n) (equal keys) | Θ(n log n) | O(n log n) |
Bubble sort | Y | Ω(n) comparisons, Ω(1) swaps | Θ(n2) comparisons, Θ(n2) swaps | О(n2) comparisons, О(n2) swaps |
Selection sort | N | Ω(n2) comparisons, Ω(n) swaps | Θ(n2) comparisons, Θ(n) swaps | О(n2) comparisons, О(n) swaps |
Tree sort | Y | Ω(n log n) | Θ(n log n) | О(n2) (unbalanced) O(n log n) (balanced) |
Shellsort | N | Ω(n log n) | depends on gap sequence | О(n2) (worst known gap sequence), O(n(log n)2) (best known gap sequence) |
Bucket sort | Y* | Ω(n + k) | Θ(n + k) | О(n2) |
Radix sort (d digits, each from 0..k) | Y* | Ω(d(n + k)) | Θ(d(n + k)) | О(d(n + k)) |
Counting sort (max value k) | Y | Ω(n + k) | Θ(n + k) | O(n + k) |