1.思想

先分割再合并，先让分割的部分有序，再全局有序。

2代码实现

2.1递归实现

public class Test {
   public static void main(String[] args)  {
       int[] a = {12,5,3,89,54,37};
       process(a,0,5);
       for (int x:a
            ) {
           System.out.print(x+" ");
       }
   }
   public static void process(int[] a,int L, int R){
       if(L==R)
           return;
       int mid= L+((R-L)>>1);
       process(a, L,mid);
       process(a,mid+1, R);
       merge(a,L,mid,R);
   }
   public static void merge(int[] arr,int L, int mid,int R){
       int[] help = new int[R-L+1];
       int i = 0;
       int p1 = L;
       int p2= mid+1;
       while (p1<=mid&&p2<=R){
           if(arr[p1]<=arr[p2]){
               help[i] = arr[p1];
               i++;
               p1++;
           }
           else {
               help[i] = arr[p2];
               i++;
               p2++;
           }
       }
       while (p1<=mid)
           help[i++] = arr[p1++];
       while (p2<=R)
           help[i++]= arr[p2++];
       for(i = 0;i < help.length;i++)
           arr[L+i] = help[i];
   }
}

2.2 非递归实现

   public static void mergesort(int[] arr)
   {
       if(arr==null || arr.length<2)
           return;
       int mergesize = 1; //组长度
       int N = arr.length;

       while (mergesize<N){
           int L = 0;
           while (L<N){
               int M = L+mergesize-1;
               if(M>=N)
                   break;
               int R = Math.min(M+mergesize,N-1);
               merge(arr,L,M,R);
               L = R+1;
           }
           if(mergesize>N/2)//防止溢出
               break;
           mergesize<<=1;
       }

   }