Is there an O(n) integer sorting algorithm?
Solution 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.
Solution 2
Comparison sorts must be at least Ω(n log n) on average.
However, counting sort and radix sort scale linearly with input size – because they are not comparison sorts, they exploit the fixed structure of the inputs.
Solution 3
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
Solution 4
These hardware-based sorting algorithms:
A Comparison-Free Sorting Algorithm
Sorting Binary Numbers in Hardware - A Novel Algorithm and its Implementation
Laser Domino Sorting Algorithm - a thought experiment by me based on Counting Sort with an intention to achieve O(n)
time complexity over Counting Sort's O(n + k)
.
Solution 5
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.
Karussell
Co-Founder of GraphHopper. Try the route planner demo based on the GraphHopper Directions API.
Updated on July 09, 2022Comments
-
Karussell almost 2 years
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.