c 和 Python 实现归并排序（递归，非递归）
C:
#include <iostream>
using namespace std;
#define MAXSIZE 9
typedef struct
{
int r[MAXSIZE+1];
int length;
}SqList;
//递归实现归并排序
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++) //两个序列，i第一个序列起点，j=m+1第二个序列起点
{
if (SR[i]<SR[j])
TR[k]=SR[i++]; //第一个序列的第一个比第二个序列的第一个小，所以赋值然后i+,取第一个序列的下一个
else
TR[k]=SR[j++];
}
if(i<=m)
{
for (l=0;l<=m-i;l++)
TR[k+l]=SR[i+l];
}
if(j<=n)
{
for (l=0;l<=n-j;l++)
TR[k+l]=SR[j+l];
}
}
void MSort(int SR[],int TR1[],int s,int t )
{
int m;
int TR2[MAXSIZE+1];
if (s==t)
{
TR1[s]=SR[s];
}
else
{
m=(s+t)/2;
MSort(SR,TR2,s,m);
MSort(SR,TR2,m+1,t);
Merge(TR2,TR1,s,m,t); //传三个参数目的 起点，分离点 ，终点
}
}
void MergeSort(SqList *L)
{
MSort(L->r,L->r,1,L->length);
}
//非递归实现归并排序
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 MergeSort2(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;
}
}
int main()
{
SqList* L = ( SqList* ) malloc( sizeof( SqList ) );//分配内存，初始化
L ->length=9;
for(int i=1;i<=L->length;i++)
{
cin>>L ->r[i];
}
for(int i=1;i<=L->length;i++)
{
cout<<L ->r[i];
}
MergeSort(L);
//MergeSort2(L);
for(int i=1;i<=L->length;i++)
{
cout<<L ->r[i];
}
}
Python：
L3=[0,50,10,90,30,70,40,80,60,20]
def Merge(SR,TR,i,m,n):
j=m+1
k=i
while (i<=m and j<=n):
if(SR[i]<SR[j]):
TR[k]=SR[i]
i=i+1
else:
TR[k]=SR[j]
j=j+1
k=k+1
if i<=m:
for l in range(0,m-i+1):
TR[k+l]=SR[i+l]
if j<=n:
for l in range(0,n-j+1):
TR[k+l]=SR[j+l]
#递归
def MSort(SR,TR1,s,t):
TR2=[0,0,0,0,0,0,0,0,0,0]
if(s==t):
TR1[s]=SR[s]
else:
m=(s+t)//2
MSort(SR,TR2,s,m)
MSort(SR,TR2,m+1,t)
Merge(TR2,TR1,s,m,t)
def MergeSort(L):
MSort(L,L,1,(len(L)-1))
#非递归
def MergePass(SR,TR,s,n):
i=1
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 in range(i,n+1):
TR[j]=SR[j]
def MergeSort2(L):
TR=[0,0,0,0,0,0,0,0,0,0]
k=1
while(k<len(L)):
MergePass(L,TR,k,len(L)-1)
k=2*k
MergePass(TR,L3,k,len(L)-1)
k=2*k
if __name__ == "__main__":
#MergeSort(L3)
MergeSort2(L3)
print(L3)
