#include <iostream>
using namespace std;
//有序表歸并算法
void merge( int r[],int s,int m,int t)
{
int tempr[50];
for(int k = s; k <= t; k++ )
tempr[k] = r[k];
int s1 = s;
int s2 = m+1;
int rs = s;
while(s1 <= m && s2 <= t)
if(tempr[s1]<=tempr[s2])
r[rs++] = tempr[s1++];
else
r[rs++] = tempr[s2++];
while(s1 <= m)
r[rs++] = tempr[s1++];
while(s2 <= t)
r[rs++] = tempr[s2++];
}
// 一趟歸并排序算法
void MergePass(int r[],int len,int n)
{
int i;
for(i=0;i+2*len-1<=n;i=i+2*len)
merge(r,i,i+len-1,i+2*len-1);
if(i+len-1<n)
merge(r,i,i+len-1,n);
}
// 歸并迭代算法
// 函數名：MergeSort；
// 參數：r[]表示想要排序的數組；tempr[]表示臨時數組；n表示數組元素個數
void MergeSort(int r[],int n)
{
int len;
len = 1;
while(len<n)
{
MergePass(r,len,n);
len = 2*len;
MergePass(r,len,n);
}
}
int main()
{
int r[14] = {10,2,12,3,4,89,5,45,21,7,90,112,78,91};
MergeSort(r,13);
for(int i=0;i<14;i++)
cout<<r[i]<<endl;
getchar();
return 0;
}