merge

//Merge: java implementation
//NlgN compares and 6NlgN array access with extra space O(N)
public class Merge {
	private static void merge(Comparable[] a, Comparablep[] aux, int lo, int mid, int hi) {
		assert isSorted(a, lo, mid );
		assert isSorted(a, mid+1, hi);
		for (int k = lo; k<=hi, k++)
			aux[k] = a[k]; //copy
		int i = lo, j = mid+1;
		for (int k = lo; k<=hi; k++) {
			if (i>mid)						a[k] = aux[j++];
			else if (j>hi) 						a[k] = aux[i++];
			else if (less(aux[j],aux[i]))				a[k] = aux[j++];
			else 							a[k] = aux[i++];
		}
		assert isSorted(a, lo, hi);
	}
	private statci void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
		if(hi <= lo) return;
		int mid = lo + (hi -lo)/2;
		sort(a, aux, lo, mid);
		sort(a, aux, mid+1, hi);
		merge(a, aux, lo, mid, hi);
	}
	public static void sort(Comparable[] a) {
		aux = new Comparable[a.length];
		sort(a, aux, 0, a.length-1);
	}
}

//Merge: java implementation(improved)
//NlgN compares and 6NlgN array access with extra space O(N)
public class Merge {
        private static void merge(Comparable[] a, Comparablep[] aux, int lo, int mid, int hi) {
                assert isSorted(a, lo, mid );
                assert isSorted(a, mid+1, hi);
                for (int k = lo; k<=hi, k++)
                        aux[k] = a[k]; //copy
                int i = lo, j = mid+1;
                for (int k = lo; k<=hi; k++) {
                        if (i>mid                      aux[k] = a[j++];//eliminate the copy to 
                        else if (j>hi)                 aux[k] = a[i++];//the auxiliary array
                        else if (less(aux[j],aux[i]))  aux[k] = a[j++];//save time but not space
                        else                           aux[k] = a[i++]; 
                }
                assert isSorted(a, lo, hi);
        }
        private statci void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
                if (hi<=lo + CUTOFF - 1) {  // use insertion sort for small subarrays
			Insertion.sort(a, lo, hi);
			return;
		}
		int mid = lo + (hi -lo)/2;
                sort(aux, a, lo, mid);
                sort(aux, a, mid+1, hi);
		if (!less(a[mid+1],a[mid])) return; // partially-ordered arrays
                merge(a, aux, lo, mid, hi);
        }
        public static void sort(Comparable[] a) {
                aux = new Comparable[a.length];
                sort(a, aux, 0, a.length-1);
        }
}
~                       
//Bottom-up mergesort: java implementation  time O(NlgN) space O(N)
public class MergeBU {
	 private static void merge(Comparable[] a, Comparablep[] aux, int lo, int mid, int hi) {
                assert isSorted(a, lo, mid );
                assert isSorted(a, mid+1, hi);
                for (int k = lo; k<=hi, k++)
                        aux[k] = a[k]; //copy
                int i = lo, j = mid+1;
                for (int k = lo; k<=hi; k++) {
                        if (i>mid)                                              a[k] = aux[j++];
                        else if (j>hi)                                          a[k] = aux[i++];
                        else if (less(aux[j],aux[i]))                           a[k] = aux[j++];
                        else                                                    a[k] = aux[i++];
                }
                assert isSorted(a, lo, hi);
        }
	public static void sort (Comparable[] a) {
		int N = a.length;
		Comparable[] aux = new Comparable[N];
		for (int sz = 1; sz<N; sz = sz+sz)
			for( in lo = 0; lo<N-sz; lo+=sz+sz)
				merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
	}
}
	                                                                                   
~