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.
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.