What is the time complexity of counting sort?

Best case O(n + k). Average case O(n + k). Worst case O(n + k). Space complexity is O(n + k). k is the size of the value range, which is why it must be small.

Counting sort

medium

Tally the values, turn the tallies into positions with a prefix sum, then place each element directly. The comparison counter stays at zero for the whole run - this is not bound by the Ω(n log n) lower bound.

Best O(n + k)Average O(n + k)Worst O(n + k)Space O(n + k)StableNeeds extra memory

Loading the counting sort engine…

Where to go next

Radix sort

medium

Sort by the last digit, then the next, and it comes out ordered.

Bucket sort

medium

Scatter by value range, sort each bucket, concatenate.

Prefix sums

easy

Precompute once, answer every range query in O(1).