Tuesday, November 27, 2018

Sorting Algorithm Complexity Cheat Sheet


Here is a handy summary table of the time complexity of some popular sorting algorithms, which I culled from Wikipedia.


(k buckets)
Algorithm Stable Time Complexity
Best Average Worst
QuicksortN Ω(n2) Θ(n log n) O(n log n)
Merge sortY Ω(n log n) (typical)
Ω(n) (natural variant)
Θ(n log n) O(n log n)
TimsortY Ω(n) Θ(n log n) O(n log n)
HeapsortN Ω(n log n) (distinct keys)
Ω(n) (equal keys)
Θ(n log n) O(n log n)
Bubble sortY Ω(n) comparisons,
Ω(1) swaps
Θ(n2) comparisons,
Θ(n2) swaps
О(n2) comparisons,
О(n2) swaps
Selection sortN Ω(n2) comparisons,
Ω(n) swaps
Θ(n2) comparisons,
Θ(n) swaps
О(n2) comparisons,
О(n) swaps
Tree sortY Ω(n log n) Θ(n log n) О(n2) (unbalanced)
O(n log n) (balanced)
ShellsortN Ω(n log n) depends on gap sequence О(n2) (worst known gap sequence),
O(n(log n)2) (best known gap sequence)
Bucket sortY* Ω(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)
* If underlying sorting algorithm is stable.