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 b

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).