Counting sort and radix sort

In short: Counting sort and radix sort sort without comparisons and can therefore beat O(n log n) when the keys are integers from a small range.

In more detail: Comparison-based methods such as quicksort can never be better than O(n log n). Exploiting properties of the keys gets around that limit.

In Depth

• Counting sort: Counts how often each value occurs (an array of size k), derives start positions from that and writes the elements there. Runtime O(n + k), stable.
• Limit: If the value range k is huge (for example 64-bit numbers), the counting array is unusable.
• Radix sort: Sorts digit by digit, from the lowest to the highest, each time with a stable method such as counting sort. Runtime O(d · (n + b)) for d digits and base b.
• Example: 32-bit numbers with base 256: only four passes.
• Use: Sorting IDs, postal codes, fixed-length strings, graphics pipelines.
• Cost: Extra memory and a dependence on the key type.

See also: Big-O notation, Sorting