Re:Sleep sort (2011)
by duaneb on Friday December 26, 2014 @02:16AM
(#8798339)
Yea, it's linear time for n where n is the largest number—pretty sure it's unbounded in terms of numbers of elements.
[ Parent
| on HN ]
True, but writing a linear sort with bounded number of distinct elements is not really a challenge.
E.g.
Intput, T: array of n elements, m: number of distinct elements.
for i in 1..m
for j in 1..n
if( T[j] == i ) print T[j];
This is O(n * m) which is O(n) since m is a constant.