Radix Sort, значение r

Question

Пожалуйста, обратитесь к следующему коду для сортировки по основанию:

class RadixSort
{
    public static void radix_sort_uint(int[] a, int bits)
    {

        int[] b = new int[a.length];
        int[] b_orig = b;


        int rshift = 0;
        for (int mask = ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits) {

            int[] cntarray = new int[1 << bits];

            for (int p = 0; p < a.length; ++p) {
                int key = (a[p] & mask) >> rshift;
                ++cntarray[key];
            }


        for (int i = 1; i < cntarray.length; ++i)
                        cntarray[i] += cntarray[i-1];


            for (int p = a.length-1; p >= 0; --p) {
                int key = (a[p] & mask) >> rshift;
                --cntarray[key];
                b[cntarray[key]] = a[p];
            }


            int[] temp = b; b = a; a = temp;
        }


        if (a == b_orig)
            System.arraycopy(a, 0, b, 0, a.length);
    }
}

Это загружено из Википедии.

Я чувствую, что алгоритм будет работать только для значения параметра bits, который отлично делит 32. Таким образом, bits должно быть примерно 2 или 4, но не 10. Пожалуйста, дайте мне знать, если я прав.

Answer 1

Краткий ответ: Нет

Длинный ответ:

Вероятная линия путаницы:

for (int mask = ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits) {

mask <<= bits сдвигает биты mask влево на bits, дополняя нули справа. Если bits не делит 32, то полные 32 бита не будут использованы. Так что, хотя bits должно делить 32, выбор значения, которое не нарушает код.