Radix Sort (LSD)

A non-comparison, distribution sort. It stably buckets values by each digit from least- to most-significant using counting sort, rewriting the array after every digit pass. Runs in O(d·(n+k)) — linear when the key width d is small.

Best

O(d·(n+k))

Average

O(d·(n+k))

Worst

O(d·(n+k))

Space

O(n+k)

Stable

Yes