/*	I came up with this idea while reading about sifting gold
 *
 *	The program has sorted everything I have tested it with; statistically, it is sound.
 *	But we also know that, in statistics, we cannot be sure of anything.
 *	Therefore, it may not always work.
 *	Since I am unsure that my program is sound, I take no responsibility for anything ever.
 *	By the way, I am a novice programmer, so why would you even risk using this code for anything important?
 *
 *	This code may be modified, copied, etc. I don't care.
 */

public class SiftSort2Algorithm extends SortAlgorithm
{
	void sort(int[]l1)throws Exception
	{
		double mean=0;
		for(int i:l1)
			mean+=i;
		sift(l1,0,l1.length,mean/l1.length);
	}private void sift(int[]l1,int left,int right,double sum)throws Exception
	{
		if(right-left<2)return;
		double meanleft=0,meanright=0;
		int count=0;


		int i=left,j=right;
		while (i<j)
		{
			if (stopRequested)return;
			else if (l1[j]<=sum)
			{
				pause(i,j);
				while (l1[i]<sum)
				{
					pause(i,j);	
					i++;
				}
				int hold=l1[i];
				meanleft += (l1[i]=l1[j]);
				meanright+= (l1[j--]=hold);
				count++;
			}
			else meanright += l1[j--];
		}

//		if(count>0)
		{
			sift(l1,left,left+i,meanleft/i);
			sift(l1,left+i,right,meanright/j);
		}
	}
}