Hello everyone, I'm trying to write a radix sort to sort a list of pointers using the values contained in objects which are pointed to in the list.

The problem is that when I run the sort, the output I receive is sorted.. for the most part. Here's an example:

...
597826833 -12781782 1240765482 806629478 1511056153 Zhmch
597921334 621119584 546779285 946641175 429392969 ycMJP
597915337 -1666338235 1541415942 -1280461245 1249811900 UbnFe
597899888 -2053271569 2005885120 -1250775138 1599174112 dMRzV
597977004 2060673011 -1887942791 489182193 -302166179 KNqlO
597966312 -638329649 1108805499 -106745408 -1363719375 tmPLo
598202374 2115522262 -1861057290 328991199 1741509466 NphiS
598193940 1540599666 -891555121 -1719530524 934950151 nbzrF
...

Clearly that is not the order those values should be in. I have written another version of the sort (one which deals with smaller arrays of values) and that one works perfectly.

My hashing algorithm works for the array version of the program so I'm fairly certain it is not at fault. Currently I am lost as to the cause of the problem and am trying to see whether I am simply messing up when it comes to handling pointers. I switched recently from Java to C++ and it is possible that I am handling this situation in the worst possible manner. Any suggestions and advice are appreciated. Thank you in advance. Here is my code, both the pointer-list and the array sorts:

/////////////////////////////////////////////////////////////////////////////
void sortDataList(list<Data *> &l) {

for (int a = 4; a > -1; a--){


for(int cnt = 0; cnt < 4; cnt++){

int listSize = l.size();

long Counters[256];
memset(Counters, 0, 256*sizeof(long)); // Set all counters to 0
for(list<Data *>::iterator it = l.begin(); it != l.end(); ++it){ // Loop over the input array
long c = (((*it)->getValue(a))>>(8*cnt)) & 255; // Get current byte…
Counters[c]++; // …and update counter
}

int nv; //number of negative values
if (cnt == 3){ //if on last pass
nv = 0;
for(int i=128;i<256;i++){ //negative signed numbers have first bit set to 1
nv += Counters[i];
}

}

long OffsetTable[257]; //offset table which tells the program where to place a value based on the value's counter
OffsetTable[0] = 0;
for(int i=1;i<257;i++){
OffsetTable[i] = OffsetTable[i-1] + Counters[i-1];
}

Data* result[listSize]; //an array for storing value pointers
for(list<Data *>::iterator it = l.begin(); it != l.end(); ++it){
long num = (((*it)->getValue(a))>>(8*cnt)) & 255; // Get current byte…
result[OffsetTable[num+1]-Counters[num]] = *it; //the iterator is placed in the result array based on the offset table and the counter
Counters[num]--;
}

while (!l.empty()){ //list is cleared
l.pop_front();
}

for (int cnt = 0; cnt < listSize; cnt++){ //items are added back to list in sorted (by current byte) order
l.push_front(result[cnt]);
}

}
}
////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////
long InputValues[] = {1484965084,-1211776950,-7,-1518189323,-1518083108,-1518116723};

for(int cnt = 0; cnt < 4; cnt++){

long Counters[256];
memset(Counters, 0, 256*sizeof(long)); // Set all counters to 0
for(int i =0 ; i < 6 ; i++){ // Loop over the input array
long c = (InputValues[i]>>(8*cnt)) & 255; // Get current byte…
Counters[c]++; // …and update counter
}

int nv;
if (cnt == 3){
nv = 0;
for(int i=128;i<256;i++){ //negative signed numbers have first bit set to 1
nv += Counters[i];
}
cout<<nv<<endl;
}


long OffsetTable[257];
OffsetTable[0] = 0;
for(int i=1;i<257;i++){
OffsetTable[i] = OffsetTable[i-1] + Counters[i-1];
}

long result[6];
for(int i = 0; i < 6; i++){
long num = (InputValues[i]>>(8*cnt)) & 255;
result[OffsetTable[num+1]-Counters[num]] = InputValues[i];
Counters[num]--;
}

cout<<endl;

if (cnt == 3){
for(int i = 0; i < nv; i++)
InputValues[i] = result[6-nv+i];
for(int i = nv; i < 6; i++)
InputValues[i] = result[i - nv];
}
else{
for(int i = 0; i < 6; i++){
InputValues[i] = result[i];
}
}
}

for(int i = 0; i < 6; i++){
cout<<InputValues[i]<<endl;
}
//////////////////////////////////////////////////////////////////////////////////////