Yes, Radix Sort and Counting Sort are O(N)
. They are NOT comparison-based sorts, which have been proven to have Ω(N log N)
lower bound.
To be precise, Radix Sort is O(kN)
, where k
is the number of digits in the values to be sorted. Counting Sort is O(N + k)
, where k
is the range of the numbers to be sorted.
There are specific applications where k
is small enough that both Radix Sort and Counting Sort exhibit linear-time performance in practice.