Is there an O(n) integer sorting algorithm?

Question

The last week I stumbled over this paper where the authors mention on the second page:

Note that this yields a linear running time for integer edge weights.

The same on the third page:

This yields a linear running time for integer edge weights and O(m log n) for comparison-based sorting.

And on the 8th page:

In particular, using fast integer sorting would probably accelerate GPA considerably.

Does this mean that there is a O(n) sorting algorithm under special circumstances for integer values? Or is this a specialty of graph theory?

PS:
It could be that reference [3] could be helpful because on the first page they say:

Further improvements have been achieved for [..] graph classes such as integer edge weights [3], [...]

but I didn't have access to any of the scientific journals.

Answer 1

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.

Answer 2

Counting sort: http://en.wikipedia.org/wiki/Counting_sort if your integers are fairly small. Radix sort if you have bigger numbers (this is basically a generalization of counting sort, or an optimization for bigger numbers if you will): http://en.wikipedia.org/wiki/Radix_sort

There is also bucket sort: http://en.wikipedia.org/wiki/Bucket_sort

Answer 3

Take a look at this from stack overflow, somebody had already asked a similar kind of question : Quantum sort

Answer 4

While not very practical (mainly due to the large memory overhead), I thought I would mention Abacus (Bead) Sort as another interesting linear time sorting algorithm.