Затруднение с Radix Sort

Question

[Eze]

Изучаю radix sort. Нашел следующую реализацию:

public static void radixSort(int[] arr) {
int numBytes = 4; // для интов
int cnt[][] = new int[numBytes][257];
int b[] = new int[arr.length];

for (int j = 0; j < numBytes; j++) {
// подсчитываем количество элементов для каждого значения j-го разряда
for (int i = 0; i < arr.length; i++) {
cnt[j][1 + iByteN(arr[i], j)]++;
}
//вычисляем позиции cnt[i], начиная с которых будут располагаться элементы
//с соответствующим значением j-го разряда
for (int i = 1; i < 257; i++)
cnt[j][i] += cnt[j][i - 1];

// расставляем элементы из массива a в массив b в указанном порядке
for (int i = 0; i < arr.length; i++) {
b[cnt[j][iByteN(arr[i], j)]++] = arr[i];
}
// копируем массив b на место массива a
for (int i = 0; i < arr.length; i++)
arr[i] = b[i];
//arr = b;
}
}

public static int iByteN(int n, int i) {
return (n >> (8 * i)) & 255;
}

Мне эта реализация нравится, она простая, но не могу понять, почему массиве cnt, подмассивы создаются длиной 257, а не 256 ? Ведь байт принимает значения от 0 до 255, то есть достаточно массив длиной 256 интов.

Answer 1

[jcmvbkbc]

Для того чтобы не ставить условие в
for (int i = 0; i < arr.length; i++) {
cnt[j][1 + iByteN(arr[i], j)]++;
}
?
Если сделать так, то тоже работает:

int cnt[][] = new int[numBytes][256];
                int b[] = new int[arr.length];

                for (int j = 0; j < numBytes; j++) {
                        // подсчитываем количество элементов для каждого значения j-го разряда
                        for (int i = 0; i < arr.length; i++) {
                                if (iByteN(arr[i], j) < 255)
                                        cnt[j][1 + iByteN(arr[i], j)]++;
                        }
                        //вычисляем позиции cnt[i], начиная с которых будут располагаться элементы
                        //с соответствующим значением j-го разряда
                        for (int i = 1; i < 256; i++)
                                cnt[j][i] += cnt[j][i - 1];
...