void MergeSort(int * const begin, int * const end) {

     if (begin +  >= end)

         return ;

     int m = (end - begin) / ;

     MergeSort(begin, begin + m);

     MergeSort(begin + m, end);

     Merge(begin, begin + m, end);

 }

 //不使用哨兵的版本，需判断边界条件

 void Merge(int * const first, int * const mid, int * const last) {

     vector<int> left(first, mid);

     vector<int> right(mid, last);

     int i = , j = , k = ;

     while (i != left.size() && j != right.size()) {

         if (left[i] <= right[j]) {

             *(first + k) = left[i++];

         } else {

             *(first + k) = right[j++];

         }

         ++k;

     }

     while (i != left.size()) {

         *(first + k) = left[i++];

         ++k;

     }

     while (j != right.size()) {

         *(first + k) = right[j++];

         ++k;

     }

 }

 //使用哨兵来简化代码

 void Merge(int * const first, int * const mid, int * const last) {

     vector<int> left(first, mid);

     vector<int> right(mid, last);

     left.push_back(INT_MAX);       //哨兵INT_MAX必须总是比较中的较大者

     right.push_back(INT_MAX);      //即待排序的值必须比INT_MAX小

     int i = , j = ;

     for (int k = ; k < last - first; ++k) {

         if (left[i] <= right[j]) {

             *(first + k) = left[i++];

         } else {

             *(first + k) = right[j++];

         }

     }

 }