Re:Timsort, the Python sorting algorithm
by loeg on Tuesday October 08, 2019 @07:32PM
(#21198435)
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).
[ Parent
| on HN ]
Re:Timsort, the Python sorting algorithm
by joshuamorton on Tuesday October 08, 2019 @07:51PM
(#21198542)
You 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.