--递归实现
public class HelloWorld {public static void showArray(int[] array){for(int i:array){System.out.print(i);}System.out.println();}public static void main(String[] args) {int[] n={5,2,4,1,3,9,7,8,6};int[] tmp=new int[n.length];System.out.println();showArray(n);mergeSort(n,0,n.length-1,tmp);showArray(tmp);System.out.println();}public static void mergeSort(int[] array,int p,int r,int[] tmp){System.out.println("******mergeSort******");if(p>=r){return;}int q=p+(r-p)/2;mergeSort(array,p,q,tmp);mergeSort(array,q+1,r,tmp);merge(array,p,r,tmp);}public static void merge(int[] array,int p,int r,int[] tmp){int q,i,j,t;q=p+(r-p)/2;i=p;j=q+1;t=p;while(i<=q&&j<=r){if(array[j]<array[i]){tmp[t++]=array[j++];}else{tmp[t++]=array[i++];}}while(i<=q){tmp[t++]=array[i++];}while(j<=r){tmp[t++]=array[j++];}for(i=p;i<=r;i++){array[i]=tmp[i];}}}--非递归实现