int main()
{
	srand(unsigned(time(NULL)));
	
	
	int upperLimit = 10000;
	int multipl = 1000;
	int size = 1000000;
	int *nrs = new int[size];
	for(int ix = 0 ; ix < size; ix++)
	{
		nrs[ix] = (rand()%multipl) * (rand()%upperLimit);
	}


	clock_t start,end;
	start = clock();
	primeSort(nrs,size);
	end = clock() - start;
	cout<<"Prime sort : "<<end<<endl;

	
	delete [] nrs;
	system("pause");
	return 0;
}

void primeSort(int arr[], int size)
{
	int primeCount,primeProduct,currentPrime;
	currentPrime = 1;
	primeProduct = currentPrime;
	primeCount = 0;
	while(primeProduct < size/3)
	{
		currentPrime = nextPrime(currentPrime);
		primeProduct *= currentPrime;
		primeCount++;
	}

	int *occ = new int[primeProduct];
	int *primes = new int[primeCount];
	currentPrime = 1;
	for(int ix = 0 ; ix < primeCount ; ix++)
	{
		currentPrime = nextPrime(currentPrime);
		primes[ix] = currentPrime;
	}
	
	
	int index,
		currentProduct,
		currentOrder,
		nextOrder,
		border,
		count;
	
	bool flag = true;
	border = count = currentOrder = 0;
	nextOrder = 1000000;

	while(flag)
	{
		for(int ix = 0 ; ix < primeProduct; ix++)
		{
			occ[ix] = 0;
		}
		border = 0;
		flag = false;
		for(int ix = count ; ix < size-border; ix++)
		{
			while(arr[ix] >= primeProduct*(currentOrder+1) && ix < size-(border+1))
			{
				if(arr[ix] / primeProduct < nextOrder)
				{
					nextOrder = arr[ix] / primeProduct;
				}
				border++;
				swap(arr[size-border],arr[ix]);
				flag = true;
			}
			if(arr[ix] < primeProduct*(currentOrder+1))
			{
				index = 0;
				for(int z = 0; z < primeCount; z++)
				{
					currentProduct = arr[ix] % primes[z];
					for(int z_n = z + 1 ; z_n < primeCount; z_n++)
					{					
						currentProduct *= primes[z_n];
					}
					index += currentProduct;
				}
				occ[index]++;
			}
		}

		for(int ix = 0 ; ix < primeProduct; ix++)
		{
			index = 0;
			for(int z = 0; z < primeCount; z++)
			{
				currentProduct = ix % primes[z];
				for(int z_n = z + 1 ; z_n < primeCount; z_n++)
				{
					currentProduct *= primes[z_n];
				}
				index += currentProduct;
			}
			while(occ[index] > 0)
			{
				arr[count++] = ix + primeProduct*currentOrder;
				occ[index]--;
			}
		}

		currentOrder = nextOrder;
		nextOrder = 10000000;
	}

	
	delete [] occ;
	delete [] primes;

}


*** Trivial function, one could sieve or initiate directly
int nextPrime(int current)
{
	int result = current;
	bool status = false;
	while(!status)
	{
		result++;
		status = true;
		for(int ix = (int)pow(result,0.5); ix > 1; ix--)
		{
			if(result % ix == 0)
			{
				status = false;
			}
		}
	}
	return result;
}

http://sortwithprimes.webs.com/
Deeper description on how it works.

Sorting integers with primes

sort, code, c++

C++