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. ;)
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.
Also consider the case of sorting n tuples that contain a non-unique number 0..k, with k << n: you can now create your dictionary in O(n) time by using a multidimensional array (k arrays of length n plus some counters; smarter solutions are probably possible) and "serializing" to a normal array.