1 #include "radixSort.h"
  2  
  3  namespace SCore {
  4  
  5      /* sort keys included in the src array, keep original untouched */
  6      /* the sorted indices of the src keys is written in inddst */
  7  	void radixSort( unsigned int *src, unsigned int *inddst, unsigned int sz )
  8  	{
  9  	    /* because we don't change the src array, we're forced to allocate a
 10  	        couple of arrays for the ping pong sorting process */
 11  		unsigned int *tmpsrc = new unsigned int [sz];
 12  		unsigned int *tmpsrc2 = new unsigned int [sz];
 13          /* This is used to store the indices in the src array */
 14  		unsigned int *tmpind = new unsigned int [sz];
 15  
 16          /* statistics for each byte */
 17  		unsigned int stat[4][256];
 18  		/* destination indice for the scattering operation */
 19  		unsigned int dest[4][256];
 20  
 21          /* initialize statistics to zero */
 22  		for (unsigned int j=0; j<4; j++)
 23  		{
 24  			for (unsigned int i=0; i<256; i++)
 25  			{
 26  				dest[j][i] = 0;
 27  				stat[j][i] = 0;
 28  			}
 29  		}
 30  
 31          /* first O(n) pass, in order to gather byte statistics */
 32  		for (unsigned int i=0; i<sz; i++)
 33  		{
 34  			unsigned int a = src[i];
 35  			unsigned int b0 = a & 0xFF;
 36  			unsigned int b1 = (a>>8) & 0xFF;
 37  			unsigned int b2 = (a>>16) & 0xFF;
 38  			unsigned int b3 = (a>>24) & 0xFF;
 39  
 40  			inddst[i] = i;
 41  
 42  			stat[0][b0] ++;
 43  			stat[1][b1] ++;
 44  			stat[2][b2] ++;
 45  			stat[3][b3] ++;
 46  		}
 47  
 48          /* calculate the destination indice in dest array */
 49  		for (unsigned int j=0; j<4; j++)
 50  		{
 51  			for (unsigned int i=1; i<256; i++)
 52  			{
 53  				dest[j][i] = stat[j][i-1];
 54  				stat[j][i] += stat[j][i-1];
 55  			}
 56  		}
 57  
 58          /* O(n) highest significant byte sorting pass */
 59  		for (unsigned int i=0; i<sz; i++)
 60  		{
 61  			unsigned int b3 = (src[i] >> 24) & 0xFF;
 62  			tmpsrc[dest[3][b3]] = src[i];
 63  			tmpind[dest[3][b3]] = inddst[i];
 64  			dest[3][b3]++;
 65  		}
 66  
 67          /* O(n) second byte sorting pass */
 68  		for (unsigned int i=0; i<sz; i++)
 69  		{
 70  			unsigned int b2 = (tmpsrc[i] >> 16) & 0xFF;
 71  			tmpsrc2[dest[2][b2]] = tmpsrc[i];
 72  			inddst[dest[2][b2]] = tmpind[i];
 73  			dest[2][b2]++;
 74  		}
 75  
 76          /* O(n) 3rd byte sorting pass */
 77  		for (unsigned int i=0; i<sz; i++)
 78  		{
 79  			unsigned int b1 = (tmpsrc2[i] >> 8) & 0xFF;
 80  			tmpsrc[dest[1][b1]] = tmpsrc2[i];
 81  			tmpind[dest[1][b1]] = inddst[i];
 82  			dest[1][b1]++;
 83  		}
 84  
 85          /* O(n) lowest significant byte sorting pass */
 86  		for (unsigned int i=0; i<sz; i++)
 87  		{
 88  			unsigned int b0 = tmpsrc[i] & 0xFF;
 89  			//tmpsrc2[dest[0][b0]] = tmpsrc[i];
 90  			inddst[dest[0][b0]] = tmpind[i];
 91  			dest[0][b0]++;
 92  		}
 93  
 94          /* cleanup memory */
 95  		delete [] tmpsrc2;
 96  		delete [] tmpsrc;
 97  		delete [] tmpind;
 98  	}
 99  
100  };