编辑代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void MergeData(int* arr,int left,int mid,int right,int* s)
{int begin1=left;
int end1=mid-1;
int begin2=mid;
int end2=right-1;
int count=left;
while(begin1<=end1&&begin2<=end2){
if(arr[begin1]<=arr[begin2]){
s[count]=arr[begin1];
begin1++;
}else{
s[count]=arr[begin2];
begin2++;
}
count++;
}
while(begin1<=end1){
s[count]=arr[begin1];
count++;
begin1++;
}
while(begin2<=end2){
s[count]=arr[begin2];
count++;
begin2++;
}
}
void MergeSort(int* arr,int left,int right,int* s){
if(right-left<=1){
return;
}
int mid=left+(right-left)/2;
MergeSort(arr,left,mid,s);
MergeSort(arr,mid,right,s);
MergeData(arr,left,mid,right,s);
memcpy(arr+left,s+left,sizeof(arr[0])*(right-left));}
void MergeSortNonR(int* arr,int size){
int* s=(int*)malloc(sizeof(arr[0])*size);
int gap=1;
while(gap<size){
int i=0;
for(;i<size;i+=2*gap){
int left=i;
int mid=left+gap;
if(mid>size){
mid=size;
}
int right=mid+gap;
if(right>size){
right=size;
}
MergeData(arr,left,mid,right,s);
}
gap*=2;
memcpy(arr,s,sizeof(arr[0])*size);
}
}
void Print(int* arr,int size){
int i=0;
for(;i<size;i++){
printf("%d ",arr[i]);
}
printf("\n");
}
int main(){
int arr[]={11,9,3,20,56,32};

MergeSortNonR(arr,sizeof(arr)/sizeof(arr[0])); 
Print(arr,sizeof(arr)/sizeof(arr[0]));
return 0;
}