归并排序

    public void mergeSort(int[] a,int low,int high){
        //可以看到，当切割到只剩一个元素时，开始进行合并
        if(low<high){
            //找到数组中的中间点，把数组分为两部分
            int mid=(low+high)/2;
            //对左边进行mergeSort操作
            mergeSort(a,low,mid);
            //对右边进行mergeSort操作
            mergeSort(a,mid+1,high);
            //合并左右两部分
            merge(a,low,mid,high);
        }
    }

    void merge(int[] a,int low,int mid,int high){
        for(int i=low;i<=high;i++){
            //缓冲空间，
            buf[i]=a[i];
        }
        //i，j分别是左指针和右指针
        int i,j,k;
        //比较左右两边的元素，谁小谁放在前面
        for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
            if(buf[i]<=buf[j])
                a[k]=buf[i++];
            else if(buf[i]>buf[j])
                a[k]=buf[j++];
        }
        //当一边全部比较完成后，另一边的元素就直接送到a的后面
        while(i<=mid)
            a[k++]=buf[i++];
        while(j<=high)
            a[k++]=buf[j++];
    }