归并排序思维导图：
知识点：如果原序列中两个数的值是相同的，它们在排完序后，它们的位置不发生变化，那么这个排序是稳定的。快速排序是不稳定的，归并排序是稳定的。
快排变成稳定的=>使快排排序数组中的每个数都不同，将ai变成<ai, i>这个二元组，将ai的下标也放进来，使用双关键字排序。
快速排序平均时间复杂度是O(nlogn)，最坏是O(n2)，但是基本上不会达到的。归并排序时间复杂度O(nlogn)。
归并排序算法模版：
1 #include <iostream> 2 3 using namespace std; 4 5 const int N = 1e5 + 10; 6 7 int n; 8 int q[N], tmp[N]; 9 10 void merge_sort(int q[], int l, int r) 11 { 12 if (l >= r) return; 13 14 int mid = l + r >> 1; 15 16 merge_sort(q, l, mid), merge_sort(q, mid + 1, r); 17 18 int k = 0, i = l, j = mid + 1; 19 while (i <= mid && j <= r) 20 if (q[i] <= q[j]) tmp[k++] = q[i++]; 21 else tmp[k++] = q[j++]; 22 while (i <= mid) tmp[k++] = q[i++]; 23 while (j <= r) tmp[k++] = q[j++]; 24 25 for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; 26 } 27 28 int main() 29 { 30 scanf("%d", &n); 31 for (int i = 0; i < n; i++) scanf("%d", &q[i]); 32 33 merge_sort(q, 0, n - 1); 34 35 for (int i = 0; i < n; i++) printf("%d ", q[i]); 36 37 return 0; 38 }