## Linear-Time Sorting

There are sorting algorithms that run faster than
O(*n *lg* n*)
time but they require special assumptions about the input sequence to be sort.
Examples of sorting algorithms that run in linear time are counting sort, radix
sort and bucket sort. Counting sort and radix sort assume that the input
consists of integers in a small range. Whereas, bucket sort assumes that the
input is generated by a random process that distributes elements uniformly over
the interval.

Since we already know that the best comparison-based sorting can to is
Ω(*n *lg* n*).
It is not difficult to figure out that linear-time sorting algorithms use operations
other than comparisons to determine the sorted order.

Despite of linear time usually these algorithms are not very desirable from
practical point of view. Firstly, the efficiency of linear-time algorithms
depend on the keys randomly ordered. If this condition is not satisfied, the
result is the degrading in performance. Secondly, these algorithms require extra
space proportional to the size of the array being sorted, so if we are dealing
with large file, extra array becomes a real liability. Thirdly, the "inner-loop"
of these algorithms contain quite a few instructions, so even though they are
linear, they would not be as faster than quick sort (say).