排序原理:。

①将待排序元素尽量拆分为元素相等的两个子组，再将子组进行拆分，直到子组元素个数为1为止。
②将相邻两个子组合并为一个有序的大组。
③重复合并，最终只有一个大组。

时间复杂度：

最好情况：O(nlogn)
最坏情况：O(nlogn)
平均情况：O(nlogn)

空间复杂度：

O(1)

稳定性：

稳定

实现：

API设计:

①主排序算法用于排序
public static void sort(int[] a)
②对数组从low到high位置的元素进行排序
private static void localSort
③将索引low到mid的子组和索引mid+1到索引high的两个子组合并为一个大组。
priavte static void merge(int[] b,int low,int mid,int high)
④ 比较API，用于比较两个元素大小
private static boolean greater(int[] a,int v,int w)
⑤交换API，用于交换两个索引位置的值
private static void exchange(int[] a,int i,int j)

API实现:

  public static void sort(int[] a) {
           int low = 0;
           int high = a.length-1;
           //初始调用排序
           localSort(a,low,high);
       }
    //对数组从low到high位置的元素进行排序
       private static void localSort(int[] a,int low,int high) {
           //安全性校验
           if(low >= high) {
               return;
           }
           //将数据分为两个组
           int mid = low + (high - low)/2;
           
           //递归调用localSort,对每组数据进行排序
           localSort(a,low,mid);
           localSort(a,mid+1,high);
           
           //对数据进行合并
           merge(a,low,mid,high);
       }
       
    //将索引low到mid的子组和索引mid+1到索引high的两个子组合并为一个大组。此时才对比交换来排序
    private static void merge(int[] b,int low,int mid,int high) {
        //定义三个指针，分别指向两个子数组和辅助数组
        int index= low;
        int[] assist = null;
        int p1 = low;
        int p2 = mid + 1;
        //移动子数组指针，将两个指针所在位置的值中较小的值加入辅助数组。
        while(p1<=mid && p2<=high) {
            if(greater(b,p1,p2)) {
                //p1位置元素大于p2位置元素，加入p2
                assist[index ++] = b[p2 ++];
            }else {
                assist[index ++] = b[p1 ++];
            }
        }
        
        //遍历子数组，若一个子数组遍历完成，则将另一个数组剩余元素按顺序追加到辅助数组中。
        while(p1 < mid) {
            assist[index ++] = b[p1 ++];
        }
        while(p2 < high) {
            assist[index ++] = b[p2 ++];
        }
            
        
        //将辅助数组中元素拷贝到合并后大数组中
            for(int position = low; position <= high;position ++) {
                b[position] = assist[position];
            }
    }
     //比较API，用于比较两个元素大小
       private static boolean greater(int[] a,int v,int w) {
           if(a[v]>a[w]) {
               return true;
           }
           return false;
           
       }
       //交换API，用于交换两个索引位置的值
       private static void exchange(int[] a,int i,int j) {
           int temp = a[i];
           a[i] = a[j];
           a[j] = temp;
           
       }