Rapasoft.eu

public class MergeSort {
	public static void main(String[] args) {
		int[] a={10,2,5,1,8,14,3,65};
		mergesort(a);
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+",");
		}
	}
	
	public static void mergesort(int[] a) {
		mergesort(a, 0, a.length - 1);
	}

	private static void mergesort(int[] a, int l, int r) {
		// base case: a[l..r] is empty or has only one element
		if (l >= r)
			return;
		// recursion step: a[l..r] is not empty
		// divide into sublists and merge
		int m = (l + r) / 2;
		mergesort(a, l, m);
		mergesort(a, m + 1, r);
		merge(a, l, m, r);
	}

	// merges to sublists
	private static void merge(int[] a, int l, int m, int r) {
		// base case: second sublist is empty
		if (m + 1 > r)
			return;
		int[] b = new int[a.length];
		// create temporary array
		// copy a[l..m] to b[l..m]
		for (int i = l; i != m + 1; i++) {
			b[i] = a[i];
		}
		// copy a[m+1..r] to b[m+1..r] in reverse order
		for (int i = m + 1; i != r + 1; i++) {
			b[i] = a[r + m + 1 - i];
		} // merge b[l..m] with b[m+1..r] to a[l..r]
		int k = l;
		int j = r;
		// pointer wandering from outside inward
		for (int i = l; i != r + 1; i++) {
			if (b[k] <= b[j])
				a[i] = b[k++];
			else
				a[i] = b[j--];
		}
	}
}