import java.util.Calendar;

public class MeargeSort {

	int[] y ;

	public long merge_sort(int[] x) {
		Calendar befor = Calendar.getInstance();
		int[] y = new int[x.length];
		mergeSort(x, 0, x.length - 1);
		Calendar after = Calendar.getInstance();
		return (after.getTimeInMillis() - befor.getTimeInMillis());
	}

	private void mergeSort(int[] x, int left, int right) {

		int mid = (left + right) / 2;

		if (right != left) {
			mergeSort(x, left, mid);
			mergeSort(x, mid + 1, right);
		}

		merge(x, left, mid, right);
	}

	private void merge(int[] x, int left, int mid, int right) {

		// if(left==right &&left ==mid) y[left]=x[left];
		// else{
		int i, j, k;
		k = mid + 1;
		i = left;
		j = left;
		while (j <= mid && k <= right) {
			if (x[j] >= x[k])
				y[i++] = x[j++];
			else
				y[i++] = x[k++];
		}
		if (j <= mid)
			while (j <= mid)
				y[i++] = x[j++];
		else
			while (k <= right)
				y[i++] = x[k++];
		// }
		for (int l = left; l <= right; l++) {
			x[l] = y[l];
		}
	}

	// hello
	public long radix_sort(int[] x) {
		Calendar befor = Calendar.getInstance();
		LinkedList[] x1 = new linkedList[10];
		linkedList[] x2 = new LinkedList[10];
		LinkedList[] put;
		LinkedList[] pull;
		int max = findMax(x);
		int signif = 1;
		signif = (String.valueOf(max)).length();
		put = x1;
		for (int i = 0; i < x.length; i++) {
			if (put[x[i] % 10] == null)
				put[x[i] % 10] = new linkedList();
			put[x[i] % 10].addLast(x[i]);
		}
		put = x2;
		pull = x1;

		for (int k = 2; k <= signif; k++) {
			for (int p = 0; p < pull.length; p++) {
				if (pull[p] != null) {
					while (pull[p].getFirst() != null) {
						int temp = (Integer) pull[p].getFirst();
						if (put[(temp % (int) Math.pow(10, k)) / (int) Math.pow(10, k - 1)] == null)
							put[(temp % (int) Math.pow(10, k)) / (int) Math.pow(10, k - 1)] = new linkedList();
						put[(temp % (int) Math.pow(10, k)) / (int) Math.pow(10, k - 1)].addLast(temp);
						pull[p].removeFirst();

					}
				}

			}
			if (pull == x1) {
				pull = x2;
				put = x1;
			} else {
				pull = x1;
				put = x2;
			}

		}
		int end = x.length - 1;
		for (int y = 0; y < pull.length; y++)
			if (pull[y] != null) {
				while (pull[y].getFirst() != null) {
					x[end--] = (Integer) pull[y].getFirst();
					pull[y].removeFirst();
				}
			}
		Calendar after = Calendar.getInstance();
		return (after.getTimeInMillis() - befor.getTimeInMillis());
	}

	private static int findMax(int[] x) {
		int max = x[0];
		for (int i = 1; i < x.length; i++)
			if (x[i] > max)
				max = x[i];
		return max;
	}

}