Any deterministic general sorting algorithm has average case time complexity @L \Omega(n\log{}n) @L . However, certain sorting algorithm can run faster in @L O(n) @L but with limitation. Instead of comparision-based sort, each element is looked individually by its value. Radix sort is one fine example of integer sorting.

Suppose, we have large directory containing names of people in random order. The names need not be distinct. We need to sort the name in the ascending order. Also our algorithm should run in linear time. A sample of the input file is shown below...