/*
 * Gamasort: from Joseph Gama
 *
 * This is a Radix Sort Exchange routine which will work only on
 * unsigned integers (unlike a general sorting function which
 * works based on comparisons).  Since its complexity overhead
 * is pretty large, it is efficient on big array where the
 * maximum number is bounded by a relatively small ceiling.
 * E.g. a big array of bytes or shorts.
 * 
 * The algorithm is pretty simple:
 * 1) It will first find the maximum and minimum radices in order to see
 *    if it can skip some radices.  Then it proceeds to order
 *    from the numbers with the most-significant set-bit downwards
 * 2) It leaves the unsorted segments of length == CUTOFF unsorted.
 * 3) From higher bit to lower it will compare numbers
 *    based on the bit being scanned.  This process is
 *    improved by using 2 pivots that will move 0's to the
 *    left and 1's to the right.
 * 4) When finding the pivots it looks for the best case
 *    of all 0's or 1's to skip more scanning.
 * 5) A low overhead Insertion Sort finishes the job.
 *
 * To make it an O(n*log(n)) algorithm in which the 'n'
 * is proportional to the largest number in the sorted array
 * requiers commenting            Call InSort(t(), 1, up)
 * and also commenting            (up-lo>CUTOFF)AND
 * Which is clearly detailed in the code
 *
 * in this version, instead of including sort.h, SWAP and Insort were taken from
 * "A library of internal sorting routines" by Ariel Faigon
 * (http://www.yendor.com/programming/sort/)
 *
 *
 *this file compiled and executed fine on both GNU () and Microsoft (VC++)
 */

#include <iostream.h>
#include <stdlib.h>
//in this version, instead of including sort.h, SWAP and Insort were taken from 
//"A library of internal sorting routines" by Ariel Faigon
//(http://www.yendor.com/programming/sort/)

#define SWAP(x, y) temp = (x); (x) = (y); (y) = temp//Swaps the contents of 2 variables
#define GT(x, y) ((x) > (y))//Greater Than
#define CUTOFF 15 //above this number there will be 2 recursive calls with 2 sub arrays
#define ArrayDimension 100000 //how many numbers to be tested

void verify (int a[],int i, int j)
{
	int x, IndexError;
		for (x=i;x<j;x++)
		{
			IndexError=x;
			if (a[x]>a[x+1])
				break;		
			}
	if (IndexError == j-1)
		cout<<"Array sorted properly!"<<endl;	
	else
		cout<<"ERROR, array not sorted properly!"<<endl;
}

void  insort (int array[], int len)
{
	register int	i, j;
	register int	temp;

	for (i = 1; i < len; i++) {
		/* invariant:  array[0..i-1] is sorted */
		j = i;
		/* customization bug: SWAP is not used here */
		temp = array[j];
		while (j > 0 && GT(array[j-1], temp)) {
			array[j] = array[j-1];
			j--;
		}
		array[j] = temp;
	}
}

//
// Recursive version of GamaSort
//
static void GamaSort( int array[], int lo, int up, int lbit, int ubit )
//lo and up are the indexes of the sub-array to be ordered
//lbit is lowest bit to be scanned, if all elements of the array are >8, lbit=3
//ubit is the current bit being scanned
{
	register int	temp;
    register long	b, r, l;
	//b is the integer that is 2 to the power of the current bit being scanned
	//r is the index of the right pivot
	//l is the index of the left pivot
	if ((up-lo>CUTOFF)&&(ubit>=lbit)){//(up-lo>CUTOFF)&& can be removed if k log n is desired for all cases
		//keep going only if 
		//a)the sub-array is greater than the cutoff point
		//b)the current bit is not smaller than the lowest bit
		b=(1<<ubit);//b=2^ubit
		r=up;l=lo;//2 pivots
		while(((b & array[r])==b)&&(r>lo))
			r--;//check 1's from the right
		if (!((r==lo)&&((b & array[r])==b)))
			while(((b & array[l])==0)&&(l<up))l++;//check 0's from the left
		if(((r==lo)&&((b & array[r])==b))||((l==up)&&((b & array[l])==0)))
			GamaSort(array, lo, up, lbit, ubit-1);//if it's all 0's or 1's, skip it
		else{
			//this is where the swapping occurs
			while(l<r){
				if(((b & array[l])==b)&&((b & array[r])==0)){
					SWAP(array[r],array[l]);
					while(((b & array[r])==b)&&(r>lo))
						r--;
				}
			l++;
		}
		if (l>=r)
			r++;
		//recursivelly sort the 2 blocks corresponding to the sorted 
		//sub-arrays but now for a lower radix
		if(r-1>lo)
			GamaSort(array, lo, r-1, lbit, ubit-1 );//left
		if (up>r)
			GamaSort(array, r, up , lbit, ubit-1 );//right
	}
	}
}

//
// Main version of gamasort (call this one)
//
void GamaSortStarter( int  array[], int up )
{
	register int  i,ubit=1,counter,n=0,lbit=0,l=1;
	for (counter=0;counter<=up;counter++)
		n|=array[counter];
	if((n & 1)==0){
		i=1;
		while((n & (1<<i))==0)i++;
		lbit=i;
	}
	while((1<<ubit)<=n)
		ubit++;
	ubit--;
	GamaSort(array, 0, up, lbit,ubit);
	insort(array, up);//if (up-lo>CUTOFF)&& was removed then this line should be removed as well
						//if k log n is desired for all cases
}

main()
{
	int c,array[ArrayDimension];
	for(c=0;c<ArrayDimension;c++)
		array[c]=rand();
	GamaSortStarter(array,ArrayDimension);
	verify(array,0,ArrayDimension);
	return 0;
}