Radix Sort base 256 Performance

Я пытаюсь реализовать сортировку Radix с базой 256 с использованием списков. Сортировка работает нормально, но сортировка больших массивов занимает много времени, кроме того, сложность должна быть линейной, O (n), но я не получаю этот результат, так как синхронизирую сортировку в выводе. Вот мой код:

Вставить функцию:

//insert to the back of the list element pointed to by x
void insert(Item * ls, Item * x)
{
x->prev = ls->prev;
ls->prev->next=x;
x->next=ls;
ls->prev=x;
}

Удалить функцию:

//delete link in list whose address is x
void delete_x(Item * x)
{
x->prev->next = x->next;
x->next->prev = x->prev;
delete [] x;
}

Функция Radix_Sort:

void radix_sort_256(unsigned int *arr,unsigned int length)
//Radix sort implementation with base 256
{

int num_of_digits=0,count=0,radix_num=0;
unsigned int base=0,largest=0;

Item List [256];             //Creating 256 Nodes ( Base 256 )
for(int j=0; j<256;j++)      // Sentinel Init for each Node
{
List[j].key=0;
List[j].next=&List[j];
List[j].prev=&List[j];
}

for(unsigned int i=0; i<length ; i++)     //Finding the largest number in the array
{
if(arr[i]>largest)
largest = arr[i];
}

while(largest != 0 )        //Finding the total number of digits in the bigest number( "largest" ) of the array.
{
num_of_digits++;
largest = largest >> 8;
}
for(int i=0; i<num_of_digits; i++)
{
Item *node;
for(unsigned int j=0; j<length; j++)
{
node = new Item;                      //Creating a new node(Total 256 nodes) and inserting numbers from the array to each node
node->next = NULL;                    // with his own index.
node->prev = NULL;
node->key = arr[j];
radix_num = ( arr[j] >> (8*i) ) & 0xFF;
insert(&List[radix_num],node);
}

for(int m=0 ; m<256 ; m++)              //checking the list for keys // if key found inserting it to the array in the original order
{
while( List[m].next != &List[m] )
{
arr[count]=List[m].next->key;
delete_x(List[m].next);             //deleting the Item after the insertion
count++;
}
}
count=0;
}
}

Главный:

void main()
{
Random r;
int start,end;
srand((unsigned)time(NULL));

// Seting up dinamic array in growing sizes,
//  filling the arrayes with random
for(unsigned int i=10000 ; i <= 1280000; i*=2)
{
// numbers from [0 to 2147483646] calling the radix
//  sort function and timing the results
unsigned int *arr = new unsigned int [i];
for(int j=0 ; j<i ; j++)
{
arr[j] = r.Next()-1;
}
start = clock();
radix_sort_256(arr,i);
end = clock();
cout<<i;
cout<<"               "<<end-start;
if(Sort_check(arr,i))
cout<<"\t\tArray is sorted"<<endl;
else
cout<<"\t\tArray not sorted"<<endl;

delete [] arr;
}
}

Кто-нибудь может увидеть, может быть, я делаю некоторые ненужные действия, которые требуют много времени для выполнения?