参考代码
#include <stdio.h>
#include <stdlib.h>
void dis(int arr[], int len){
int i = 0;
for(; i < len; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
void merge(int arr[],int temp[],int left,int mid,int right){
// 标记左半区第一个未排序
int l=left;
// 标记右半区第一个未排序
int r=mid+1;
// 临时记录
int pos=left;
while(l<=mid && r<=right){
if(arr[l]<arr[r]){
temp[pos++]=arr[l++];
}else{
temp[pos++]=arr[r++];
}
}
// 合并左半区剩下的
while(l<=mid){
temp[pos++]=arr[l++];
}
// 合并右半区剩下的
while(r<=right){
temp[pos++]=arr[r++];
}
// 合并后的复制回原数组
while(left<=right){
arr[left]=temp[left];
left++;
}
}
void ms(int arr[],int temp[],int left,int right){
if(left<right){
int mid=(left+right)/2;
// 递归划分左半区
ms(arr,temp,left,mid);
// 递归划分右半区
ms(arr,temp,mid+1,right);
// 合并
merge(arr,temp,left,mid,right);
}
}
//主入口函数
void mergeSort(int arr[],int len){
int* temp=(int*)malloc(len*sizeof(int));
if(temp){
ms(arr,temp,0,len-1);
free(temp);
}
}
int main () {
int arr[]={9,5,2,7,12,4,3,1,11};
int len=9;
dis(arr,len);
mergeSort(arr,len);
dis(arr,len);
return 0;
}