1. ## 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.