#include
        
         using namespace std;const int maxn = 5000;int main(){    void merge_sort(int a[], int beg, int end);    void put(int a[], int n);    int a[maxn], n;    cout << "Enter a number: ";    cin >> n;    cout << "Enter some numbers:" << endl;    for(int i = 0; i < n ; ++i)        cin >> a[i];    merge_sort(a, 0, n-1);    put(a, n);    return 0;}void merge(int a[], int beg, int mid, int end){//合并，小技巧用到哨兵    int n1 = mid - beg + 1, n2 = end - mid;    int L[n1+1], R[n2+1];    for(int i = 0; i < n1; ++i)        L[i] = a[beg+i];    L[n1] = 50000;   //哨兵元素    mid = mid + 1;    for(int i = 0; i < n2; ++i)        R[i] = a[mid+i];    R[n2] = 50000;   //哨兵元素    int i=0, j =0, k = beg;    //------------------块一----------------------------------    for(int k = beg; k <= end; ++k)    {//当同时遇到哨兵意味着所有牌已经合并        if(L[i] <= R[j])        {            a[k] = L[i];            ++i;        }        else        {            a[k] = R[j];            ++j;        }    }    //------------------块一----------------------------------}void merge_sort(int a[], int beg, int end){    //将n个元素分成各个汗n/2个元素的子问题    int mid = (beg+end)/2;    if(beg < end)    {        merge_sort(a, beg, mid);        merge_sort(a, mid+1, end);        merge(a, beg, mid, end);    }}void put(int a[], int n){    for(int i = 0; i < n; ++i)        cout << a[i] << "  ";    cout << endl;}/*81 2 6 4 7 9 3 5*//*//块一也可以不适用哨兵元素，方法如下，但不如哨兵代码简洁！   while(i < n1 && j < n2)   {//不使用哨兵元素       if(L[i] <= R[j])       {           a[k] = L[i];           ++i;       }       else       {           a[k] = R[j];           ++j;       }       ++k;   }   while(i < n1)   {       a[k] = L[i];       ++k;       ++i;   }   while(j < n2)   {       a[k] = R[j];       ++k;       ++j;   }   //注：//虽然使用a[k++]=L[i++];也能得出正确结果，但最好还是不用这种形式，   //因为这类表达式的行为在C/C++中是“没有明确定义的”，这种未定义的   补充知识：C++中，规定了操作数计算顺序的操作符有条件操作符(?:),逗号操作符(,)、   逻辑与操作符(&&)以及逻辑或操作符(||),除此之外，其他操作符并未指定其操作数的   其值顺序，例如表达式f1()*f2();在做乘法操作之前必须调用f1函数和f2函数，然而，我们却无法知道到底是先调用f1还是先调用f2。又如if(a[index++] < a[index]);如果index为0，则可能是0与0比较，又或者是0与1比较。具体依赖于编译器的选择（基于”实现效率“的提高），在不同编译器、不同情况下，选择的结果可能不同，一次应尽量避免使用此类未定义的表达式。       */
        

比拟起牌的过程……

时间复杂度:T(n) = Θ(nlgn);