归并排序算法

来源：百度知道 编辑：UC知道 时间：2024/05/18 10:38:27
【问题描述】
归并排序（Merging Sort）算法是一种优秀的稳定的算法，教材上给出了递归形式2－路归并算法，虽然形式上简洁，但是实用性很差。试设计一非递归形式2－路归并排序算法。
【算法要求】
要求实现的算法的时间复杂度不大于 ，辅助存储空间不大于 。
要求用C语言完成

两种归并排序算法的实现：二路归并排序和基本归并排序（虚拟消除递归的二路归并排序）
#define ARRAY_SIZE 1024

int B[1024]; //使用一个全局变量，避免归并排序中每次都重新申请和释放空间造成的开销

template <typename T>
void Merge(T A[], int l, int m, int h)
{
int i = l;
int j = m+1;
int k = 0;

while(i<=m&&j<=h)
{
if(A[i]<A[j])
{
B[k++] = A[i];
i++;
}
else
{
B[k++] = A[j];
j++;
}
}

while(i<=m)
{
B[k++] = A[i++];
}

while(j<=h)
{
B[k++] = A[j++];
}

for(i=l; i<=h; i++)
{
A[i] = B[i-l];
}
}

//二路归并排序的实现

template <typename T>
void MergeSort(T a[], int l, int h)
{
int m = (h+l)/2;
if(l>=h)
{