3 ms·
It doesn't necessarily have to prepare that dictionary (e.g. when sorting n tuples that contain a unique number 0..n). Also consider the case of sorting n tupl
by JoachimSchipper 16y ago
It doesn't necessarily have to prepare that dictionary (e.g. when sorting n tuples that contain a unique number 0..n).
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.
- jsharpe 16y agoThere 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.