/* Given the source code for the method merge(). Write the recursive method of Merge sort .
 */

public class T05Q3answer {

	public static void main (String [] arg) {
		int[] a = new int[arg.length];
		for (int i=0; i<arg.length; i++) {
			a[i] = Integer.parseInt(arg[i]);
		}
		int start = 0;
		int end = a.length;
		mergeSort (a, start, end);
		for (int i=0; i<a.length; i++)
		System.out.print(a[i] + " ");
	}

	public static void mergeSort (int[] a, int start, int end) {

/* please complete this merge sort method here: */

		if (start < end - 1) {
			int mid = (start + end)/2;
			mergeSort(a, start, mid);
			mergeSort(a, mid, end);
			merge(a, start, mid, end);
		}
	}

	private static void merge(int[] a, int start, int mid, int end) {
		int temp[] = new int[end-start];
		int i = start;
		int j = mid;
		for(int k = 0; k < temp.length; k++) {
			if (j >= end || i < mid && a[i] <= a[j])
				temp[k] = a[i++];
			else
				temp[k] = a[j++];
		}
		for(int k = start; k < end; k++)
			a[k] = temp[k-start];
	}
}