编辑代码

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

void Merge_pass(int a[],int *tempA,int N,int length);
void Merge_sort(int a[],int N);
void Merge1(int a[],int *tempA,int L,int R,int RightEnd);

void Merge1(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++];
    }
}

void Merge_sort(int a[],int N){
    //初始化子序列（有序子序列）的长度
    int length = 1;
    int *tempA;
    tempA = malloc(N * sizeof(int));
    if(tempA != NULL){
        while(length < N){
            Merge_pass(a,tempA,N,length);
            length *= 2;
            Merge_pass(tempA,a,N,length);
            length *=2;
        }

        for(int i = 0;i < N;i++){
        printf("%d ",a[i]);
    }

        free(tempA);
    }else{
        printf("空间不足");
    }
}

/*
   非递归算法：
     一趟的归并
     length：当前有序子列的长度
*/
void Merge_pass(int a[],int *tempA,int N,int length){
    int i,j;
    /*
      一对一对的归并，正好归并完成的一个前提条件是
      要归并的子序列正好是偶数个，正好是成对的，若
      是奇数个就会出现一个“尾巴”
      i <= N-2*length：保证前面成对的那一部分先归并，
      处理到倒数第二对
      i += 2*length:跳过两段找下一对
    */
    for(i = 0;i <= N-(2*length);i += 2*length){
        /*将a中的元素归并到TmpA，有序的
          内容在tempA中
          i+length:下一段的起始位置
          i+2*length-1：下一段的终止位置
        */
        Merge1(a,tempA,i,i+length,i+(2*length-1));
    }
    /*
      处理“尾巴”
      i加上一段 < N说明最后有两个子列
    */
    if(i + length < N){
        //归并最后2个子列
        Merge1(a,tempA,i,i+length,N-1);
    }
    //最后只剩1个子列
    else{
        for(j = i;j < N;j++){
            tempA[j] = a[j];
        }
    }
}

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);
}