import java.util.ArrayList;

    // for ints
	public static int[] mergesort(int[] stuff) {
//		(define (mergesort l)
//				   (cond ((< (length l) 2) l)
//				         (else (merge (mergesort (partition1 l))
//				                      (mergesort (partition2 l))))))
		if (stuff.length < 2) {
			return stuff;
		} else {
			return merge(mergesort(partition1(stuff)), mergesort(partition2(stuff)));
		}
	}

	private static int[] merge(int[] arr1, int[] arr2) {
//		(define (merge l1 l2)
//				   (cond ((null? l1) l2)
//				         ((null? l2) l1)
//				         ((< (car l1) (car l2))
//				            (cons (car l1) (merge (cdr l1) l2)))
//				         (else (cons (car l2) (merge l1 (cdr l2))))))
		int[] merged = new int[arr1.length + arr2.length];

		int a1index = 0, a2index = 0;
		int mergedIndex = 0;
		while (a1index < arr1.length && a2index < arr2.length) {
			if (arr1[a1index] < (arr2[a2index])) {
				merged[mergedIndex++] = arr1[a1index++];
			} else {
				merged[mergedIndex++] = arr2[a2index++];
			}
		}
		while (a1index < arr1.length)
			merged[mergedIndex++] = arr1[a1index++];
		while (a2index < arr2.length)
			merged[mergedIndex++] = arr2[a2index++];
		return merged;
	}

	public static int[] partition1(int[] stuff) {
//		(define (partition1 l)
//				   (let ((num-elements (round (/ (length l) 2))))
//				      (define (part counter l)
//				         (cond ((= counter num-elements) ())
//				               (else (cons (car l) (part (+ counter 1) (cdr l))))))
//				      (part 0 l)))

		int[] tmp = new int[stuff.length / 2];

		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = stuff[i];
		}
		return tmp;
	}

	public static int[] partition2(int[] stuff) {
		int[] tmp = new int[stuff.length - (stuff.length / 2)];

		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = stuff[i + (stuff.length/2)];  // copy 2nd half of stuff array
		}
		return tmp;
	}

    // for arrays
	public static Comparable[] mergesort(Comparable[] stuff) {
//		(define (mergesort l)
//				   (cond ((< (length l) 2) l)
//				         (else (merge (mergesort (partition1 l))
//				                      (mergesort (partition2 l))))))	
		if (stuff.length < 2) {
			return stuff;
		} else {
			return merge(mergesort(partition1(stuff)), mergesort(partition2(stuff)));
		}
	}
	
	private static Comparable[] merge(Comparable[] arr1, Comparable[] arr2) {
//		(define (merge l1 l2)
//				   (cond ((null? l1) l2)
//				         ((null? l2) l1)
//				         ((<(car l1) (car l2))
//				            (cons (car l1) (merge (cdr l1) l2)))
//				         (else (cons (car l2) (merge l1 (cdr l2))))))
		Comparable[] merged = new Comparable[arr1.length + arr2.length];

		int a1index = 0, a2index = 0;
		int mergedIndex = 0;
		while (a1index < arr1.length && a2index < arr2.length) {
			if (arr1[a1index].compareTo(arr2[a2index]) < 0) {
				merged[mergedIndex++] = arr1[a1index++];
			} else {
				merged[mergedIndex++] = arr2[a2index++];
			}
		}
		while (a1index < arr1.length)
			merged[mergedIndex++] = arr1[a1index++];
		while (a2index < arr2.length)
			merged[mergedIndex++] = arr2[a2index++];
		return merged;
	}

	private static Comparable[] partition1(Comparable[] stuff) {
//		(define (partition1 l)
//				   (let ((num-elements (round (/ (length l) 2))))
//				      (define (part counter l)
//				         (cond ((= counter num-elements) ())
//				               (else (cons (car l) (part (+ counter 1) (cdr l))))))
//				      (part 0 l)))

		Comparable[] tmp = new Comparable[stuff.length / 2];

		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = stuff[i];
		}
		return tmp;
	}

	private static Comparable[] partition2(Comparable[] stuff) {
		Comparable[] tmp = new Comparable[stuff.length - (stuff.length / 2)];

		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = stuff[i + (stuff.length/2)];  // copy 2nd half of stuff array
		}
		return tmp;
	}
	
	
	
    // for ArrayLists
	public static ArrayList<Comparable> mergesort(ArrayList<Comparable> alist) {
		if (alist.size() < 2)
			return alist;
		else {
			return merge(mergesort(left(alist)), mergesort(right(alist)));
		}	
	}

	private static ArrayList<Comparable> merge(ArrayList<Comparable> alist1,
			ArrayList<Comparable> alist2) {
		ArrayList<Comparable> alist = new ArrayList<Comparabl>>();

		while (alist1.size() > 0 && alist2.size() > 0) {
			if (alist1.get(0).compareTo(alist2.get(0)) < 0) {
				alist.add(alist1.remove(0));
			} else {
				alist.add(alist2.remove(0));
			}
		}
		while (alist1.size() > 0)
			alist.add(alist1.remove(0));
		while (alist2.size() > 0)
			alist.add(alist2.remove(0));
		return alist;
	}

	public static ArrayList<Comparable> left(ArrayList<Comparable> alist) {
		ArrayList<Comparable> tmp = new ArrayList<Comparable>();
		int numElements = (int) Math.ceil(alist.size() / 2.0);

		for (int i = 0; i < numElements; i++) {
			tmp.add(alist.get(i));
		}
		return tmp;
	}

	public static ArrayList<Comparable> right(ArrayList<Comparable> alist) {
		int index = (int) Math.ceil(alist.size() / 2.0);
		int numElements = alist.size() / 2;  // Extra element goes in 

		ArrayList<Comparable> tmp = new ArrayList<Comparable>();

		for (int i = 0; i < numElements; i++) {
			tmp.add(alist.get(index + i));
		}
		return tmp;
	}
}