public class Mergesort {

	public void mergesort(int[] array)
	{
		mergesort(array, 1, array.length);
	}

	public void mergesort(int[] array, int p, int r)
	{
		if(p < r)
		{
			int q = (p + r)/2;
			mergesort(array, p, q);
			mergesort(array, q + 1, r);
			merge(array, p, q, r);
		}
	}

	public void merge(int[] array, int p, int q, int r)
	{
		int n = q - p + 1;
		int m = r - q;
		int[] leftArray = new int[n + 1];
		int[] rightArray = new int[m + 1];
		for(int i = 1; i < n; i++)
		{
			leftArray[i] = array[p + i - 1];
		}
		for(int j = 1; j < m; j++)
		{
			rightArray[j] = array[q + j];
		}

		leftArray[n + 1] = -1;
		rightArray[m + 1] = -1;
		int i = 1;
		int j = 1;
		for(int k = p; k < r; k++)
		{
			if(leftArray[i] <= rightArray[j])
			{
				array[k] = leftArray[i];
				i = i + 1;
			}
			else
			{
				array[k] = rightArray[j];
				j = j + 1;
			}
		}
	}

}