Radix sort not sorting properly when given lots of numbers

Question

I have to implement a Binary Radix sort for my assignment. While I have made it work, it stops properly sorting (doesn't actually sort them) once it hits a larger amount of numbers (usually 300+). Does anyone know what the problem is?

vector<unsigned char> A; //gets input from file that we have been given, containing 1000 numbers
vector<unsigned char> C(2);
vector<unsigned char> B(A.size());

for (int i = 0; i < A.size(); i++) {
    B.push_back(0);
}

for (int k = 0; k < 8; k++) {
    C[0] = 0;
    C[1] = 0;

    for (int i = 0; i < A.size(); i++) {
        C[((int)A[i] >> k) & 1]++;
    }

    C[1] += C[0];

    for (int j = A.size() - 1; j >= 0; j--) {
        B[--C[(int)(A[j] >> k) & 1]] = (int)A[j];
    }

    std::swap(A, B);
}

After doing some testing, it seems that the limit is 256 numbers. So when it goes above 256 numbers, the algorithm can't sort it anymore

Answer 1

Look at declarations and usage

vector<unsigned char> C(2);
B[--C[(int)(A[j] >> k) & 1]]

Any element C[i] contains N between 0 and 255. Thus the index --C[(int)(A[j] >> k) & 1] is always less than 255.

Solution:

vector<size_t> C(2);