2021-04-25

算法：

// 先拆分为n个小数组：
void msort(int[] arr,int left,int right){
if(left>=right) return;
int mid = left+(right-left)/2;
msort(arr,left,mid-1);
msort(arr,mid+1,right);
// 合并
merge(arr,left,mid,right);
}

void merge(int[] arr,int left,int mid,int right){
// 临时数组
int[] temp = new int[right-left+1];
int p1 = left;
int p2 = mid+1;
int p = 0;
while(p1<=mid && p2<=right){
        if(arr[p1]>arr[p2]){temp[p++]=arr[p2++];}
        else temp[p++]=arr[p1++];
    }
while(p1<=mid) temp[p++]=arr[p1++];
while(p2<=right) temp[p++]=arr[p2++];

// 把临时数组的值赋到结果：
for(int i=0;i<temp.length;i++){
    arr[i+left] = temp[i];
}
}