1 #include <iostream>
 2 #include <vector>
 3 #include <time.h>
 4 #include <sys/timeb.h>
 5 using namespace std;
 6 
 7 constexpr int MAX = 20;
 8 // 创建随机排序数组
 9 vector<int> CreateArray()
10 {
11     vector<int> array(MAX);
12     srand((unsigned int)time(NULL));
13     for (auto &val : array) {
14         val = rand() % MAX;
15     }
16     return array;
17 }
18 
19 void PrintArray(const vector<int> &array)
20 {
21     for (const auto &val : array) {
22         std::cout << val << " ";
23     }
24     std::cout << endl;
25 }
26 // 合并算法 从小到大
27 void Merge(vector<int> &array, int start, int mid, int end, vector<int> &result)
28 {
29     // 左边分组区间
30     int leftStart = start;
31     int leftEnd = mid;
32     // 右边分组区间
33     int rightStart = mid + 1;
34     int rightEnd = end;
35     // 辅助空间元素个数
36     int length = 0;
37     while (leftStart <= leftEnd && rightStart <= rightEnd) {
38         if (array[leftStart] < array[rightStart]) {
39             result[length] = array[leftStart];
40             length++;
41             leftStart++;
42         } else {
43             result[length] = array[rightStart];
44             length++;
45             rightStart++;
46         }
47     }
48     // 左区间剩余元素
49     while (leftStart <= leftEnd) {
50         result[length] = array[leftStart];
51         length++;
52         leftStart++;
53     }
54     // 右区间剩余元素
55     while (rightStart <= rightEnd) {
56         result[length] = array[rightStart];
57         length++;
58         rightStart++;
59     }
60     // 排序后的辅助空间元素覆盖原空间
61     for (int i = 0; i < length; i++) {
62         array[start + i] = result[i];
63     }
64 }
65 // 合并排序
66 void MergeSort(vector<int> &array, int start, int end, vector<int> &result)
67 {
68     // 递归出口
69     if (start >= end) {
70         return;
71     }
72     int mid = start + (end - start) / 2;
73     // 左边分组
74     MergeSort(array, start, mid, result);
75     // 右边分组
76     MergeSort(array, mid + 1, end, result);
77     // 左右区间排序后合并
78     Merge(array, start, mid, end, result);
79 }
80 int main()
81 {
82     vector<int> myArray = CreateArray();
83     // 排序前
84     std::cout << "Before sort:" << endl;
85     PrintArray(myArray);
86     int length = myArray.size();
87     vector<int> result(length);
88     MergeSort(myArray, 0, length - 1, result);
89     // 排序后
90     std::cout << "After sort:" << endl;
91     PrintArray(myArray);
92     system("pause");
93     return 0;
94 }

运行结果：