News for hackers. Stuff that matters.
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.
Re:Timsort, the Python sorting algorithm by loeg on Tuesday October 08, 2019 @09:56PM (#21199242)
Sorry, my mistake -- you're totally right. Number of bits is log_2(k), where k is just the maximal key number.