归并排序,它有两大核心操作.
- 一个是将数组一分为二,一个无序的数组成为两个数组。
- 另外一个操作就是,合二为一,将两个有序数组合并成为一个有序数组。
时间复杂度情况：
最好和最快情况都是:O(NlogN)
代码模版如下
int arr[N], temp[N];
void merge_sort(int arr[], int l, int r) {
if (l >= r)
return;
//递归结束条件
int mid = l + r >> 1;
merge_sort(arr, l, mid), merge_sort(arr, mid + 1, r);
//递归处理子问题
int k = 0, i = l, j = mid + 1;
//归并
while (i <= mid && j <= r) {
if (arr[i] <= arr[j])
temp[k ++] = arr[i ++];
else
temp[k ++] = arr[j ++];
}
//收尾
while (i <= mid)
temp[k ++] = arr[i ++];
while (j <= r)
temp[k ++] = arr[j ++];
for (int i = l, j = 0; i <= r; i++, j++)
arr[i] = temp[j];
}图解如下：
更详细的见下面的连接：