非递归实现归并排序算法

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//排序用到的结构和函数
#define MAXSIZE 20
typedef struct
{
int r[MAXSIZE+1];   //用于存储要排序的数组，r[0]用作哨兵或者临时变量
int length; //用于记录顺序表的长度
}SqList;

//交换L中数组r的下标为i和j的值
void swap(SqList * L,int i,int j)
{
int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}




//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
void Merge(int SR[],int TR[],int i,int m,int n)
{
int j,k,l;
for(j=m+1,k=i;i<=m && j<=n;k++) //将SR中记录由小到大归并入TR
    {
if(SR[i]<SR[j])
            TR[k]=SR[i++];
else
            TR[k]=SR[j++];
    }
if(i<=m)
    {
for(l=0;l<=m-i;l++)
            TR[k+l]=SR[i+l];    //将剩余的SR[i..m]复制到TR(注意这里的是字母l)
    }
if(j<=n)
    {
for(l=0;l<=n-j;l++)
            TR[k+l]=SR[j+l];    //将剩余的SR[j..n]复制到TR(注意这里的是字母l)
    }
}


//将SR[]中相邻长度为s的子序列两两归并到TR[]
void MergePass(int SR[],int TR[],int s,int n)
{
int i=1;
int j;
while(i<=n-2*s+1)
    {
        Merge(SR,TR,i,i+s-1,i+2*s-1);   //两两归并
        i=i+2*s;
    }
if(i<n-s+1) //归并最后两个序列
        Merge(SR,TR,i,i+s-1,n);
else    //若最后只剩下单个子序列
for(j=i;j<=n;j++)
            TR[j]=SR[j];
}







//非递归实现归并排序
void MergeSort(SqList * L)
{
int * TR=(int *)malloc(L->length * sizeof(int));    //申请额外空间
int k=1;
while(k<L->length)
    {
        MergePass(L->r,TR,k,L->length);
        k=2*k;  //子序列长度加倍
        MergePass(TR,L->r,k,L->length);
        k=2*k;  //子序列长度加倍
    }

}




//输出元素
void print(SqList * L)
{
for(int i=1;i<=L->length;i++)
    {
printf("%d ",L->r[i]);
    }
printf("\n");
}



int main()
{
int n;
    SqList L;
    L.length=0; //初始化length的长度
printf("请输入元素个数：\n");
scanf("%d",&n);
    srand(0);
for(int i=1;i<=n;i++)
    {
        L.r[i]=rand()%100+1;
        L.length++;
    }
printf("排序前的数组: ");
    print(&L);
    MergeSort(&L);
printf("排序后的数组: ");
    print(&L);

}