Thread: MSD vs. LSD radix sort

Hello, After reading Prelude's sorting tutorial (www.eternallyconfuzzled.com) I wrote MSD radix sort function for sorting array of integeres.

Code:

void MSD_radix_sort_r ( int a[], int aux[], int first, int last, int d )
{
       if ( d >= 0 )
	{  
		int i, count[UCHAR_MAX + 2] = {0}; 
		
    		for ( i = first; i <= last; i++ ) 
    		{
      			count[digit ( a[i], d ) + 1]++;
		} 
    		for ( i = 1; i <= UCHAR_MAX; i++ )
		{	 
      			count[i] += count[i - 1];
		} 
    		for ( i = first; i <= last; i++ )
		{ 
      			aux[count[digit ( a[i], d )]++] = a[i];
		} 
    		for ( i = first; i <= last; i++ )
		{ 
			a[i] = aux[i - first];
		} 
		
    		MSD_radix_sort_r ( a, aux, first, first + count[0] - 1, d - 1 );
    	
    		for (i = 0; i < sizeof ( int ); i++) 
		{
      			MSD_radix_sort_r ( a, aux, first + count[i], first + count[i + 1] - 1, d - 1 ); 
		}	
		
	}
}
void MSD_radix_sort ( int a[], int first, int last )
{
	int d = sizeof ( int ) - 1;
	int* aux = malloc ( ( last - first + 1 ) * sizeof ( int ) );
	
	MSD_radix_sort_r ( a, aux, first, last, d );	
	
	free ( aux );
}

where digit is macro defined as:
#define digit(kljuc,i) ( ( kljuc ) >> ( ( i ) * CHAR_BIT ) & UCHAR_MAX )

As to be expected because of the MSD (most significant digit) algorithm only after first few steps array is almost sorted.
I tested both LSD and MSd algorithm (LSD is implemented in the tutorial) with random numbers between 0 and 999999. I notice that
there is a significat difference in execution time. However both execution time for 500000 elements were rather small:
LSD 0.078s
MSD 0.048s
so I don't know if this is reliable.

Here's my complete program:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

#define N 500000
#define digit(kljuc,i) ( ( kljuc ) >> ( ( i ) * CHAR_BIT ) & UCHAR_MAX )
typedef void ( *pFunkcija ) ( int [], int, int ); 

void MSD_radix_sort_r ( int a[], int aux[], int first, int last, int d )
{
	if ( d >= 0 )
	{  
		int i, count[UCHAR_MAX + 2] = {0}; 
		
    		for ( i = first; i <= last; i++ ) 
    		{
      			count[digit ( a[i], d ) + 1]++;
		} 
    		for ( i = 1; i <= UCHAR_MAX; i++ )
		{ 
      			count[i] += count[i - 1];
		} 
    		for ( i = first; i <= last; i++ )
		{ 
      			aux[count[digit ( a[i], d )]++] = a[i];
		} 
    		for ( i = first; i <= last; i++ )
		{ 
			a[i] = aux[i - first];
		} 
		
    		MSD_radix_sort_r ( a, aux, first, first + count[0] - 1, d - 1 );
    	
    		for (i = 0; i < sizeof ( int ); i++) 
		{
      			MSD_radix_sort_r ( a, aux, first + count[i], first + count[i + 1] - 1, d - 1 ); 
		}	
		
	}
}
void MSD_radix_sort ( int a[], int first, int last )
{
	int d = sizeof ( int ) - 1;
	int* aux = malloc ( ( last - first + 1 ) * sizeof ( int ) );
	
	MSD_radix_sort_r ( a, aux, first, last, d );	
	
	free ( aux );
}
void LSD_radix_sort ( int a[], int first, int last )
{
	int i, j, d = sizeof ( int ) - 1 ;	
	int* aux = malloc ( ( last - first + 1 ) * sizeof ( int ) );

	for ( j = 0; j <= d  ; j++ )
	{	
		int count[UCHAR_MAX + 2] = { 0 };
		
		for ( i = first; i <= last; i++ )
		{
			count[digit ( a[i], j ) + 1]++;
		}
		for ( i = 1; i < UCHAR_MAX + 1; i++ )
		{
    			count[i] += count[i - 1];
		}
		for ( i = first; i <= last; i++ )
		{
    			aux[count[digit ( a[i], j )]++] = a[i];
		}
		for ( i = first; i <= last; i++ )
		{
			a[i] = aux[i - first];
		}	
	}  
	free ( aux );
}

double measure_time ( pFunkcija sortiraj, int a[], int first, int last )
{
	clock_t start = clock ( );
	
	sortiraj ( a, first, last );

	return ( double )  ( clock ( ) - start ) / CLOCKS_PER_SEC ;
}
double uniformna_distribucija ( int seed )
{
	return seed * ( 1.0 / ( RAND_MAX + 1.0 ) );
}
void generate_random ( int a[], int len , int num )
{
	int i;
	
	srand ( ( unsigned int ) ( time ( NULL ) ) );
	for ( i = 0; i < len; i++ )
	{
		a [i] = ( int ) ( uniformna_distribucija ( rand ( ) ) * num );
	}
} 


int main ( void ) 
{
	int a[N];
	generate_random ( a, N, 999999 );
	printf ( "Time of execution: %gs\n", measure_time ( LSD_radix_sort, a, 0, N - 1 ) );  
	system ( "pause" );
}

I doubt these results are reliable, but I don't have other way to test it, because with more than 500000 elements I get seg fault.
I use Dev-Cpp.
I know that real strength of MSD sort is when applied on strings, but here is simple implementation applied to int array.
What do you think about this implementation?
Can you comment this?

Thank you very much