How does this very efficient Radix Sort algorithm variation work?

Revision en1, by post, 2021-08-05 21:17:49

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English post 2021-08-05 21:17:49 1188 Initial revision (published)