Sorting algorithms statistics
| Algorithm | Worst-case running time | Average-case/expected running time |
|---|---|---|
| Insertion sort | Θ(n2) | Θ(n2) |
| Merge sort | Θ(n lgn) | Θ(n lgn) |
| Heapsort | O(n lgn) | - |
| Quicksort | Θ(n2) | Θ(n lgn) (expected) |
| Counting sort | Θ(k + n) | Θ(k + n) |
| Radix sort | Θ(d (n + k)) | Θ(d (n + k)) |
| Bucket sort | Θ(n2) | Θ(n) (average-case) |
O - assymptotic upper bound.
Θ - assymptotically tight bounds.