编辑代码

#include <stdio.h>
#include <malloc.h>

void Merge_sort(int a[],int N);
void MSort(int a[],int *tempArray,int L,int RightEnd);
void Merge(int a[],int *tempArray,int L,int R,int RightEnd);

void Merge(int a[],int tempArray[],int L,int R,int RightEnd){
    int i,temp,LeftEnd,NumElemments;

    LeftEnd = R - 1;
    temp = L;
    NumElemments = RightEnd - L + 1;
    while(L <= LeftEnd && R <= RightEnd){
        if(a[L] >= a[R]){
            tempArray[temp] = a[R];
            R++;
            temp++;
        }else{
            tempArray[temp] = a[L];
            L++;
            temp++;
        }
    }
    while(L <= LeftEnd){
        tempArray[temp++] = a[L++];
    }
    //直接复制右边剩下的
    while(R <= RightEnd){
        tempArray[temp++] = a[R++];
    }

    for(i = 0;i < NumElemments;i++,RightEnd--){
        a[RightEnd] = tempArray[RightEnd];
    }
}

//统一函数接口
void Merge_sort(int a[],int N){
    /*
      若只在Merge方法中申请这个临时空间，会导致
      空间的重复申请与释放；Merge_sort中申请，
      然后做为参数传递的话，就只在该空间上进行
      操作，不会重复申请与释放空间
    */
    int *tempArray;
    tempArray = malloc(N * sizeof(int));
    if(tempArray != NULL){
     
     MSort(a,tempArray,0,N-1);
    
    for(int i = 0;i < N;i++){
        printf("%d ",a[i]);
    }
        free(tempArray);
    }else{
        printf("Error");
    }
}

/* 
   归并排序的递归算法：分而治之
*/
void MSort(int a[],int *tempArray,int L,int RightEnd){
    int Center;
    if(L < RightEnd){
        Center = (L + RightEnd)/2;
        MSort(a,tempArray,L,Center);
        MSort(a,tempArray,Center+1,RightEnd);
        Merge(a,tempArray,L,Center+1,RightEnd);
    }
}

int main () {
    int a[6] = {25,52,30,56,66,12};
    printf("排序前的元素为：\n");
    for(int i = 0;i < 6;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    printf("排序后的元素为：\n");
    Merge_sort(a,6);
}