Radix Sort base 256 Performance

Question

I'm trying to implement Radix sort with base 256 using Lists. The sort works fine but it takes to long to sort big arrays, in addition the complexity should be linear, O(n), but i'm not getting that result as i'm timing the sort in the output. Here is my code:

Insert Function:

//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 Function:

//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 Function:

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;
    }
}

Main:

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;
    }
}

Can anyone see, maybe i'm doing some unnecessary actions that take great deal of time to execute?

Answer 1

Complexity is a difficult beast to master, because it is polymorphic.

When we speak about the complexity of an algorithm, we generally simplify it and express it according to what we think being the bottleneck operation.

For example, when evaluating sorting algorithms, the complexity is expressed as the number of comparisons; however, should your memory be a tape¹ instead of RAM, the true bottleneck is the memory access and therefore a quicksort O(N log N) ends up being slower than a bubblesort O(N ** 2).

Here, your algorithm may be optimal, its implementation seems lacking: there is a lot of memory allocation/deallocation going on, for example. Therefore, it may well be that you did not identified the bottleneck operation correctly, and that all talk of linear complexity are moot since you are not measuring the right things.

¹ because tapes take a time to move from one cell to another proportional to the distance between those cells, and thus a quicksort algorithms that keep jumping around memory ends up doing a lot of back and forth whilst a bubble sort algorithm just runs the length of the tape N times (max).

Answer 2

Radix sort with base 256 could easily look something like this.

void sort(int *a, int n)
{

     int i, *b, exp = 1, max = 0;
        for (i = 0; i < n; i++) {
            if (a[i] > max)
               max = a[i];
        }

      b = (int*)malloc(n * sizeof(int));
        while (max / exp > 0) {
            int box[256] = {0};
            for (i = 0; i < n; i++)
               box[a[i] / exp % 256]++;
            for (i = 1; i < 256; i++)
               box[i] += box[i - 1];
            for (i = n - 1; i >= 0; i--)
               b[--box[a[i] / exp % 256]] = a[i];
            for (i = 0; i < n; i++)
               a[i] = b[i];
            exp *= 256;
        }
   free(b);
}