public class MergeSorter2
{
	private int[] a;

	public MergeSorter2(int[] anArray)
	{
		a = anArray;
	}

	public void sort()
	{
		if(a.length<=1) return;

		int[] first  = new int[a.length/3];
		int[] second = new int[first.length];
		int[] third  = new int[a.length-(2*second.length)];

		for(int i=0;i<first.length;i++)
		{
			first[i]=a[i];
		}
		for(int i=0; i<second.length;i++)
		{
			second[i]=a[first.length+i];
		}
		for(int i=0; i<third.length;i++)
		{
			third[i]=a[second.length+i];
		}

		MergeSorter2 firstSorter  = new MergeSorter2(first);
		MergeSorter2 secondSorter = new MergeSorter2(second);
		MergeSorter2 thirdSorter  = new MergeSorter2(third);

		firstSorter.sort();
		secondSorter.sort();
		thirdSorter.sort();

		merge(first, second, third);
	}

	public void merge(int[] first, int[] second, int[] third)
	{
		int iFirst=0, iSecond=0, iThird=0, j=0;

		while(iFirst<first.length && iSecond<second.length && iThird<third.length)
		{
			if(first[iFirst]<second[iSecond] && first[iFirst]<third[iThird])
			{
				a[j]=first[iFirst];
				iFirst++;
			}
			else if(second[iSecond]<first[iFirst] && second[iSecond]<third[iThird])
			{
				a[j]=second[iSecond];
				iSecond++;
			}
			else
			{
				a[j] = third[iThird];
				iThird++;
			}
			j++;
		}

		while(iFirst<first.length)
		{
			a[j]=first[iFirst];
			j++; iFirst++;
		}
		while(iSecond<second.length)
		{
			a[j]=second[iSecond];
			j++; iSecond++;
		}
		while(iThird<third.length)
		{
			a[j]=third[iThird];
			j++; iThird++;
		}
	}
}