归并排序

首先看两个有序数组的排序

    public static int[] merge(int[] a, int[] b) {
        int[] c = new int[a.length + b.length];
        int i = 0, j = 0, l = 0;
        while (i < a.length && j < b.length) {
            c[l++] = a[i] <= b[j] ? a[i++] : b[j++];
        }
        while (i < a.length) {
            c[l++] = a[i++];
        }
        while (j < b.length) {
            c[l++] = b[j++];
        }
        return c;
    }

归并算法：先拆分，直到只剩下一个值（本身为有序），再合并

    public static void sort(int[] a,int low,int high) {
        if(low==high)
            return; 
        int mid = (low+high)/2;
        if(low<high) {
            sort(a, low, mid);
            sort(a, mid+1, high);
            merge(a, low,mid,high);
        }
    }

    private static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high-low+1];
        int i = low;
        int j = mid+1;
        int k = 0;
        while(i<=mid&&j<=high) {
            temp[k++]=a[i]<=a[j]?a[i++]:a[j++];
        }
        while(i<=mid)
            temp[k++]=a[i++];
        while(j<=high)
            temp[k++]=a[j++];
        for(int x=0;x<temp.length;x++) {
            a[x+low] = temp[x];
        }
    }

稳定性：稳定
时间复杂度：O(nlogn)