MergeSort(集計ソート)の原理とC++コードの実現

集計ソートは、分治ポリシーを使用してソートされます.原理は以下の通り
分解:配列されるn個の要素の配列をn/2個の要素を有する2つのサブ配列に分解する.
解決:集計ソートを使用して、2つのサブシーケンスを再帰的にソートします.
≪マージ|Merge|emdw≫:ソートされた2つのサブシーケンスをマージして、ソートされた答えを生成します.
集計ソートの時間的複雑さはθ(nlgn).
集計ソートは、安定したソートの1つです.
集計ソートは元のソートではなく、集計フェーズで追加の配列空間を申請する必要があります.
コードは次のとおりです(参考まで).

1 void MergeSort(int * const begin, int * const end) {
2     if (begin + 1 >= end)
3         return ;
4     int m = (end - begin) / 2;
5     MergeSort(begin, begin + m);
6     MergeSort(begin + m, end);
7     Merge(begin, begin + m, end);
8 }

 1 //        ，       
 2 void Merge(int * const first, int * const mid, int * const last) {
 3     vector<int> left(first, mid);
 4     vector<int> right(mid, last);
 5 
 6     int i = 0, j = 0, k = 0;
 7     while (i != left.size() && j != right.size()) {
 8         if (left[i] <= right[j]) {
 9             *(first + k) = left[i++];
10         } else {
11             *(first + k) = right[j++];
12         }
13         ++k;
14     }
15     while (i != left.size()) {
16         *(first + k) = left[i++];
17         ++k;
18     }
19     while (j != right.size()) {
20         *(first + k) = right[j++];
21         ++k;
22     }
23 }

 1 //         
 2 void Merge(int * const first, int * const mid, int * const last) {
 3     vector<int> left(first, mid);
 4     vector<int> right(mid, last);
 5     left.push_back(INT_MAX);       //  INT_MAX           
 6     right.push_back(INT_MAX);      //         INT_MAX 
 7 
 8     int i = 0, j = 0;
 9     for (int k = 0; k < last - first; ++k) {
10         if (left[i] <= right[j]) {
11             *(first + k) = left[i++];
12         } else {
13             *(first + k) = right[j++];
14         }
15     }
16 }