image.png
#include <bits/stdc++.h>
using namespace std;
int N=100;
void merge(int a[],int L1,int R1,int L2,int R2){
int i=L1;
int j=L2;
int temp[N],index=0;
// 因为每个小单元都是由小到达排序的，所以只需比较最低位即可判断temp[index]对应的结果。
while(i<=R1&&j<=R2){
if(a[i]<=a[j]){
temp[index++]=a[i++];
}
else{
temp[index++]=a[j++];
}
}
// 如果i/j中有一个未达到末尾（R1/R2）（实际上只有一个没有）
// 那就把剩余的已经排好序的数组填充到temp数组后面就好了。
while(R1>=i){
temp[index++]=a[i++];
}
while(R2>=j){
temp[index++]=a[j++];
}
for(i=0;i<index;i++){
a[i+L1]=temp[i];
}
}
void mergeSort(int a[],int left,int right){
if(left<right){
int middle=(left+right)/2;
// 根据middle递归切割数组为最小单元（len=1/2）
mergeSort(a,left,middle);
mergeSort(a,middle+1,right);
// 进行迭代排序。
merge(a,left,middle,middle+1,right);
}
}
int main() {
int i,j,k;
int a[]={3,2,5,7,6,1,8,0,9,4};
mergeSort(a,0,9);
for(i=0;i<10;i++){
printf("%d\n",a[i]);
}
return 0;
}
