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