Re:Cycle Sort
by jsharpe on Monday November 22, 2010 @11:24AM
(#1930269)
There are much simpler sorts in those cases though, like just outputting (0, 1, 2, ..., n) or (0, 1, 2, ..., k). Those are O(n) without any shenanigans. ;)
[ Parent
| on HN ]
Re:Cycle Sort
by JoachimSchipper on Monday November 22, 2010 @11:33AM
(#1930315)
Yes, bucket sort is simpler and O(n) too. But your examples are too simple: think ((0, val0), (1, val1), ..., (n, valn)) and ((0, val0_1), (0, val0_2), (0, val0_3), (1, val1_1), ..., (k, valk_6)) or somesuch.