合并排序算法函数（算法导论）

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef vector<int> T;
typedef vector<int>::size_type Tsize;

void merge(T &A,Tsize p,Tsize q,Tsize r)
{
 Tsize n1=q-p+1;
 Tsize n2=r-q;

 T Ln,Rn;

 for(Tsize i=0;i<n1;i++)
  Ln.push_back(A[p+i]);

 for (Tsize j=0;j<n2;j++)
  Rn.push_back(A[q+j+1]);

 Tsize m=0,n=0;
 for(Tsize ix=p;ix<=r;ix++)
  if(m<n1&&n<n2)
   {A[ix]=Ln[m]<Rn[n] ? Ln[m++]:Rn[n++];}
  else
  {if (m<n1)
    A[ix]=Ln[m++];
   else
    A[ix]=Rn[n++];
  }
}

void merge_sort(T &A,Tsize p,Tsize r)
{
 if(p<r){
  Tsize q=(p+r)/2;

  merge_sort(A,p,q);
  merge_sort(A,q+1,r);
  
  merge(A,p,q,r);
 }
}

void output_array(T &B)
{
 for(Tsize ix=0;ix<B.size();ix++)
  cout<<B[ix]<<" ";
}

int main()
{
 T ivec;
 int temp;

 cout<<"Please input the numbers be sorted(end with Ctrl+Z): "<<endl;

 while(cin>>temp)
  ivec.push_back(temp);

 merge_sort(ivec,0,ivec.size()-1);

 cout<<"After sorted,they are: "<<endl;
 output_array(ivec);

 return  0;
}