### post's blog

By post, history, 7 weeks ago,

I'm trying to solve this problem. Here very efficient integer sorting algorithm is required. Counting sort will not work because elements can be as high as $10^9$. So the radix sort is an option, I coded my radix sort with base $10$ (like a standard approach) but got TLE.

But I found this algorithm somewhere and it works so well. Can anybody explain this? Can't get what the bit magic does here.

Algorithm

Thanks.

• +15

 » 7 weeks ago, # |   +23 It is nothing more than radix sort in base $256$. Each $32$-bit number is split into $4$ digits of $8$ bits each. Efficient because we make use of bit operations to directly obtain the digits, and $256$ is small enough to put in a bucket anyway.Similarly you can try working it in base $2^{15}$, for $2$ digits each number.