MergeSort.java

MergeSort.java

package algorithm;

public class MergeSort {
  public static void sort(int[] A,int p, int r){
		if(p < r){
			int q = (r+p)/2;
			sort(A,p,q);
			sort(A,q+1,r);
			merge(A,p,q,r);
		}
	}

	private static void merge(int[] a, int p, int q, int r) {
		//将两个序列分开存放在临时的空间内
    int[] L = new int[q-p+1];
		int[] R = new int[r-q];
		for (int i = 0; i < R.length; i++) {
			R[i] = a[p+i];
		}
		for (int i = 0; i < L.length; i++) {
			L[i] = a[q+i+1];
		}
    //打印这两个临时序列
		Utils.printArray(R,"R");
		Utils.printArray(L,"L");
    //开始 Merge 这两个序列
		for(int k = p,i=0,j=0; k < r; ){
			if(L[i]<=R[j]){
				a[k++]=L[i++];
			}else{
				a[k++] = R[j++];
			}
			
      //如果有一临时序列已经 Merge 完，那么，另外一个将会全部取出，放在排好序的序列后面
      if(i==L.length){
				for (int m = j; m < R.length; m++) {
					a[k++]=R[m];
				}
			}
			if(j==R.length){
				for (int n = i; n < L.length; n++) {
					a[k++] = L[n];
				}
			}
			Utils.printArray(a);
		}
	}
	
	public static void main(String[] args) {
		int[] A ={5,2,4,7,1,3,2,6};
		sort(A,0,A.length-1);
	}
}

Utils.printArray() can be got from the first gist.