/*TITLE distribution sorting program*/

/****keyword-flag*** "%v %f %n" */
/* "8 21-Mar-98,17:44:20 MEGAC.CPP" */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void Megasort(unsigned char **PtrArray, unsigned *RecNums, int KeyLength, 
unsigned ArraySize)
{
	unsigned char	m;
	int	 cum;
	int i;
	unsigned j;

	int	 BucketCount [ 256 ];
	int	 BucketPosition[ 256 ];
	unsigned char	**TempPtrArray;
	unsigned *TempRecNums;

/* either 0 or 1 element means no sorting required */
	if (ArraySize < 2) 
		return;

	TempPtrArray = (unsigned char **) malloc ( sizeof(unsigned char *) * ArraySize);
	if ( TempPtrArray == NULL )
		{
		printf( "out of memory\n" );
		exit( 1 );
		}
	TempRecNums = (unsigned *) malloc ( sizeof(unsigned) * ArraySize );

	if (TempRecNums  == NULL )
		{
		printf( "out of memory\n" );
		exit( 1 );
		}

	for (i = KeyLength-1; i >= 0; i-- )
		{
		memset(BucketCount,0,256*sizeof(int));

		for (j = 0; j < ArraySize; j++ )
			{
			m = PtrArray[ j ][ i ];
			++BucketCount[m];
			}

		BucketPosition[0] = 0;
		for (cum = 1; cum < 256; cum++ )
			BucketPosition[ cum ] = BucketCount[ cum-1 ] + BucketPosition[ cum-1 ];

		for (j = 0; j < ArraySize; j++ )
			{
			m = PtrArray[j][i];
			TempPtrArray[BucketPosition[m]] = PtrArray[j];
			TempRecNums[BucketPosition[m]] = RecNums[j];
			++BucketPosition[m];
			}

		memcpy(PtrArray,TempPtrArray,ArraySize*sizeof(unsigned char *));
		memcpy(RecNums,TempRecNums,ArraySize*sizeof(int));
		}

	free(TempPtrArray);
	free(TempRecNums);
}