[Explanation/Clarification] radix_sort.cc

[omar-s-ta]

Hello @nealwu,

First, I'm sorry to do it this way, but I wanted to ask about some points in the radix_sort.cpp file, specifically the radix_sort function.

I was trying to understand the point of some parts of the function, and I was hoping you might help.

1. First if condition, specifically the RHS of the || operator.
2. Why are you calculating max_bits and passes this way? I assume the function is generalized to handle -ve numbers too, but this is taken care of in lines similar to lines 54 and 55 in the function.
3. Second if condition

I'm trying to solve this problem as a practice for radix_sort with a custom base, and was studying/learning different implementations for radix_sort.

Best Regards, Omar Abdelrahman

[nealwu]

1 and #3 are just situations where we would rather do comparison sort. #2 is to smooth out the number of bits for each pass; e.g., instead of 10 bits, 10 bits, 10 bits, 2 bits, we would rather do 11 bits, 11 bits, 10 bits.

[omar-s-ta]

Thanks for your reply!

Why would we rather do comparison sorts in these situations? I'm trying to understand the reasoning behind it.

I usually see radix_sort implementations with division and modulo operators around a certain base, but this is the first time I've seen one with a little bit of bit manipulation, so I'm interested in understanding the logic/reasoning behind it and good input to think of ways to improve my library.

Thanks in advance.