post's blog

By post, history, 7 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

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.