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 post 2021-08-05 21:17:49 1188 Initial revision (published)