News for hackers. Stuff that matters.
Re:Timsort, the Python sorting algorithm by joshuamorton on Tuesday October 08, 2019 @07:50PM (#21198534)
No, radix sort is worst case O(n * k). In many common cases, k ~= log(n). IN certain specific cases, k < log(n), and specifically for cases where you have a very large n, but a bounded number of values (say, you're sorting 10 billion 4-bit ints), k can be considered a constant. But that is by no means generally true.
Re:Timsort, the Python sorting algorithm by bloomer on Tuesday October 08, 2019 @11:16PM (#21199686)
In most cases k << n. For 64-bit integers, byte wise radix sort k is 8, which is less than log n whenever n is more than 256. So, radix sort is typically much faster than an O(n log n) sort of your data support it. It just isn’t as widely used because it is not as general as a comparison based sort.
Re:Timsort, the Python sorting algorithm by Dylan16807 on Wednesday October 09, 2019 @05:40PM (#21208438)
That logic isn't right. You can implement an O(n log n) sort with whatever log base/radix you want. It could be 2, it could be 256, it could be 4096. If you use the same base/radix for both n and k, then log n is close to k and probably smaller.

Which version ends up faster is mostly based on factors that big O notation doesn't capture easily. You have to push things to impractical numbers like n=2^1000 or 2^1000000 to properly distinguish between constant factors and log factors, and at that point it doesn't actually help you write better code.

Re:Timsort, the Python sorting algorithm by joshuamorton on Tuesday October 08, 2019 @11:30PM (#21199741)
After a byte-wise radix sort you still have to sort within each bucket.

In the worst case, every element falls into a single bucket, at which point your best best is to do a bit wise radix sort over the low 8 bits.

This ends up being equivalent to k=log(n).

Re:Timsort, the Python sorting algorithm by gigatexal on Wednesday October 09, 2019 @01:05AM (#21200203)
Jumping in this fascinating thread about sorting to ask what the double less than chevrons mean? I know what one means but what do two of them mean?
Re:Timsort, the Python sorting algorithm by donbindner on Wednesday October 09, 2019 @09:28AM (#21202963)
In this context, it means "much less." It's used that way sometimes in mathematical discussions.
Re:Timsort, the Python sorting algorithm by Spiritus on Wednesday October 09, 2019 @02:20AM (#21200575)
Basically “much less than”.
Re:Timsort, the Python sorting algorithm by oh_sigh on Wednesday October 09, 2019 @01:25AM (#21200286)