伪代码请见《算法导论》2.3节
merge-sort实现：
public class MergeSort { public static void sort(double [] A,int p, int r) { if(p<r) { int q = (int) Math.floor( (p+r)/2 ); sort(A,p,q); sort(A,q+1,r); merge(A,p,q,r); } return ;
} public static void merge(double [] A, int p, int q, int r) { int n1 = q-p+1; int n2 = r-q; double [] L = new double[n1]; double [] R = new double[n2]; for(int i=0; i<n1; i++) L[i] = A[p+i]; for(int i=0; i<n2;i++) R[i]=A[q+i+1]; int i=0; int j=0; int counter = p; while(i<L.length && j<R.length) { if(L[i]<=R[j]) { A[counter]=L[i]; i++; } else { A[counter]=R[j]; j++; } counter++; } if(i==L.length) { for(int k=j;k<R.length;k++) A[counter++] = R[k]; } else { for(int k=i;k<L.length;k++) A[counter++] = L[k]; } } public static void main(String[] args) { // TODO Auto-generated method stub double [] A = {1.3, 5 ,2, 6.9, 2.0,7.8,4.3}; MergeSort.sort(A,0,A.length-1); for(double a:A) System.out.print(a+" "); }}