2 ms·
GP is talking about radix sort, basically. If you know all your keys are integers you can sort in O(n log k) (k is maximal key width in bits).
by loeg 7y ago
GP is talking about radix sort, basically. If you know all your keys are integers you can sort in O(n log k) (k is maximal key width in bits).
- joshuamorton 7y agoYou have a bit of a repetition here backwards. You can sort in O(n * k), where k is the maximal key width in bits. This ends up being O(n log(k)). Your formulation suggests radix sort running in O(n log(log(k))), which isn't quite true.
- loeg 7y agoSorry, my mistake -- you're totally right. Number of bits is log_2(k), where k is just the maximal key number.