/* 
 歸并算法：把兩個(gè)或兩個(gè)以上的線性表合并在一起，形成一個(gè)新的線性表
 函數(shù)模版的基本使用
 程序意圖：將兩個(gè)相同類型的線性表元素排好序，然后將他們組合成一個(gè)排好的線性表 
*/
#include <iostream>
using namespace std;
const int n = 5; //5個(gè)元素 
//輸出數(shù)據(jù)元素
template <class T1>
void OutPut(T1 out[(2*n)])
{ 
  for (int i=0; i<(2*n); i++)
  { 
  cout<<out[i]<<" ";
  }
  cout<<endl;
} 
//輸入數(shù)據(jù)元素 
template <class T2>
void InPut(T2 in[n])
{
  cout<<"請(qǐng)輸入5個(gè)數(shù)據(jù)元素：";
  for (int i=0; i<n; i++)
  { 
  cin>>in[i];
  cout<<" "; 
  }
  cout<<endl;
}
//模版函數(shù) 輸入線性表元素并將其排序
template <class T3> 
void MySort(T3 a[2*n])
{
  int temp; //交換數(shù)據(jù)臨時(shí)變量 
  //冒泡錨序 
  for (int i=0; i<2*n-1; i++)
  {
   for (int j=0; j<2*n-1-i; j++)
   {
    if (a[j]>a[j+1]) 
    {
    temp = a[j];
    a[j] = a[j+1];
    a[j+1] = temp; 
    }
   }
  }
}
//模版函數(shù) 歸并 
template <class T> 
void MergeList(T La[n], T Lb[n], T Lc[(2*n)]) 
{
  int i = 0; //作為L(zhǎng)a的下標(biāo) 
  int j = 0; //Lb下標(biāo)
  int k = 0; //Lc下標(biāo) 
  //將La Lb組合成在一起 
  while (i<n && j<n)
  {
   if (La[i] < Lb[j])
   {
    Lc[k] = La[i];
    k++;
    Lc[k] = Lb[j];
   }
   else
   {
    if (La[i] == Lb[j])
    {
     Lc[k] = La[i];
     k++;
     Lc[k] = Lb[j];
    }
    else
    {
     Lc[k] = Lb[j];
     k++;
     Lc[k] = La[i];
    }
   }
   //各下標(biāo)往下移動(dòng) 
   i++;
   j++;
   k++;
  } 
  //如果La中的數(shù)據(jù)沒(méi)有取完，及La比Lb長(zhǎng)，則將La剩下的元素插入Lc中 這里是進(jìn)行擴(kuò)展 
  while (i<=n)
  {
   Lc[k++] = La[i++];
  } 
  //如果Lb中的數(shù)據(jù)沒(méi)有取完，及Lb比La長(zhǎng)，則將Lb剩下的元素插入Lc中
  while (j<=n)
  {
    Lc[k++] = Lb[j++];
  } 
  //對(duì)組合好的元素進(jìn)行排序 
  MySort(Lc); 
}
int main()
{
 int a1[n],a2[n], a[(2*n)];
 double b1[n], b2[n],b[(2*n)];
 char m1[n], m2[n], m[(2*n)];
 //輸入數(shù)據(jù) 歸并輸出 
 /*InPut(a1);
 InPut(a2); 
 MergeList(a1,a2,a);
 OutPut(a); */
 InPut(m1);
 InPut(m2); 
 MergeList(m1,m2,m);
 OutPut(m); 
 system("pause");
 return 0;
}