import java.util.Random;
class MergeSort {
	private static void merge(int a[], int st, int mid, int end) {
		int b[] = new int[end-st+1]; // No of elements merged array 
		int x = st;    // Index in a[st..mid]
		int y = mid + 1; // index in a[mid+1..end]
		int j = 0; // Index in array b
		while ((x <= mid) && (y <= end)) {
			if (a[x] < a[y]) b[j++] = a[x++];
			else b[j++] = a[y++];
		}
		while (x <= mid) b[j++] = a[x++];
		while (y <= end) b[j++] = a[y++];
		for (j=st; j<=end; j++)
			a[j] = b[j-st];
	}
	private static void msort(int a[], int st, int end) {
		if (st == end) return;
		int mid = (st + end) / 2;
		msort(a, st, mid);
		msort(a, mid+1, end);
		merge(a, st, mid, end);
	}
	public static void sort(int a[]) {
		if (a == null) return;
		msort(a, 0, a.length-1);
	}
}
class SelSort {
	private static int smallestNumIndex(int a[], int st) {
		int i = st;
		int j;
		for (j = st+1; j<a.length; j++) 
			if (a[j] < a[i]) i = j;
		return i;
	}
	public static void sort(int a[]) {
		if (a == null) return;
	        int i;
		for (i=0; i < a.length; i++) {
			int t = smallestNumIndex(a, i);
			int tmp = a[t];
			a[t] = a[i];
			a[i] = tmp;
		}
	}
}

class timer {
	private long elapsedTime = 0;
	private long startTime = 0;
	private boolean isTiming = false;
	public void start() {
		if (isTiming) return;
		isTiming = true;
		startTime = System.currentTimeMillis();
	}
	public void stop() {
		if (!isTiming) return;
		isTiming = false;
		elapsedTime = System.currentTimeMillis() - startTime;
	}
	public long getElapsedTime() {
		if (isTiming) stop();
		return elapsedTime;
	}
}

class ArrayStuff {
	public static int[] randomArray(int len) {
		if (len <= 0) return null;
		int a[] = new int[len];
		Random r = new Random();
		int i;
		for (i=0; i<len; i++) 
			a[i] = r.nextInt(2*len);
		return a;
	}
	public String toString(int a[]) {
		String s = "{";
		int i;
		for (i=0; i<a.length; i++)
			s += " " + a[i];
		s += " }";
		return s;
	}
}

class test{
	public static void main(String s[]) {
	timer t = new timer();
	int a[], i;
	for (i=1000; i<100000; i=i*2) {
		a = ArrayStuff.randomArray(i);
		t.start();
		MergeSort.sort(a);
		t.stop();
		System.out.println("Merge Sort>> Size: " + i + " Time: " + t.getElapsedTime()+ " ms");
		a = ArrayStuff.randomArray(i);
		t.start();
		SelSort.sort(a);
		t.stop();
		System.out.println("Selection Sort>> Size: " + i + " Time: " + t.getElapsedTime()+ " ms");
	}
	}
}