3 ms·
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. ;)
by jsharpe 16y ago
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. ;)
- JoachimSchipper 16y agoYes, 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.