合并排序（遞歸調用）

#include <iomanip.h>//調用setw

#include <iostream.h>  //將b[0]至b[right-left+1]拷貝到a[left]至a[right]

template <class T> 

void Copy(T a[],T b[],int left,int right)

{  int size=right-left+1;

   for(int i=0;i<size;i++)

   {  

   a[left++]=b[i];

   }

}  //合并有序數組a[left:i],a[i+1:right]到b,得到新的有序數組b

template <class T> 

void Merge(T a[],T b[],int left,int i,int right)

{  int a1cout=left,//指向第一個數組開頭  

   a1end=i,//指向第一個數組結尾  

   a2cout=i+1,//指向第二個數組開頭  

   a2end=right,//指向第二個數組結尾  

   bcout=0;//指向b中的元素    

for(int j=0;j<right-left+1;j++)//執行right-left+1次循環

{  if(a1cout>a1end)

 {   b[bcout++]=a[a2cout++]; 

     continue; }  //如果第一個數組結束，拷貝第二個數組的元素到b

  if(a2cout>a2end) 

 {

    b[bcout++]=a[a1cout++];

    continue; }  //如果第二個數組結束，拷貝第一個數組的元素到b

if(a[a1cout]<a[a2cout])

{  b[bcout++]=a[a1cout++];

   continue; }  //如果兩個數組都沒結束，比較元素大小，把較小的放入b

 else 

 {  b[bcout++]=a[a2cout++];

    continue;} } }  //對數組a[left:right]進行合并排序

template <class T> 

void MergeSort(T a[],int left,int right)

 {  T *b=new

    int[right-left+1];

  if(left<right)

{ 

  int i=(left+right)/2;//取中點 

  MergeSort(a,left,i);//左半邊進行合并排序

  MergeSort(a,i+1,right);//右半邊進行合并排序

  Merge(a,b,left,i,right);//左右合并到b中

  Copy(a,b,left,right);//從b拷貝回來

 }

} 

 int main()

 { int n; 

  cout<<"請輸入您將要排序的數目:"; cin>>n; 

 int *a=new int[n];  cout<<"請輸入相應的數字：";

 for(int i=0;i<n;i++)

 {  cin>>a[i]; } 

 MergeSort( a, 0, n-1); cout<<"排序結果:";

 for(int j=0;j<n;j++)

 {  cout<<setw(5)<<a[j];  } 

    cout<<endl;

    return 1;

 }