/*
歸並排序的基本操作是將兩個或兩個以上的記錄有序序列歸並為一個有序序列。最簡單的情況是，只含一個記錄的序列顯然是個有序序列，經過"逐趟歸並"使整個序列中的有序子序列的長度逐趟增大，直至整個記錄序列為有序序列止。
二路歸並排序則是歸並排序中的一種最簡單的情況， 它的基本操作是將兩個相鄰的有序子序列"歸並"為一個有序序列， 如右側所示。這個操作對順序表而言是極其容易實現的， 只要依關鍵字從小到大進行"復制"即可，如下算法所示。
*/
#include <iostream>
using std::cout;
using std::endl;
void Merge(int *SR, int *TR, int i, int m, int n){
// 將有序的SR[i..m]和SR[m+1..n]歸並為有序的TR[i..n]
int j = m+1;
int k = i;
for(; i<=m && j<=n; ++k){// 將SR中記錄按關鍵字從小到大地復制到TR中
if (SR[i]<=SR[j]){
TR[k] = SR[i++];
}else{
TR[k] = SR[j++];
}
}
while (i<=m) TR[k++] = SR[i++]; // 將剩余的 SR[i..m] 復制到TR
while (j<=n) TR[k++] = SR[j++]; // 將剩余的 SR[j..n] 復制到TR
}//Merge
void Msort( int *SR, int *TR1, int s, int t ){
// 對SR[s..t]進行歸並排序，排序後的記錄存入TR1[s..t]
if (s==t){
TR1[s] = SR[s];
}else {
int TR2[10] ;
int m = (s+t)/2; // 將 SR[s..t] 平分為 SR[s..m] 和 SR[m+1..t]
Msort(SR,TR2,s,m); // 遞歸地將 SR[s..m] 歸並為有序的 TR2[s..m]
Msort(SR,TR2,m+1, t); // 遞歸地將SR[m+1..t]歸並為有序的TR2[m+1..t]
Merge(TR2,TR1,s,m,t); // 將TR2[s..m]和TR2[m+1..t] 歸並到 TR1[s..t]
}// else
} // Msort
int main()
{
int li[10] = {22,47,81,34,73,56,12,20,39,65};
cout<<"注意：只整個數組R[0....9]10個元素排序"<<endl;
for(int i = 0; i<=9; i++){
cout << li[i] << " ";
}
cout << endl;
Msort(li,li,0,9);
cout << endl;
for(i = 1; i<=10; i++){
cout << li[i-1] << " ";
}
cout << endl;
return 0;
}