归并排序是一个基于分治的算法。
时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 。
原问题:把数组排序。
子问题:把数组前一半、后一半分别排序,然后再合并左右两半(两个有序数组)就可以了。void mergeSort(vector<int>& arr, int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
return merge(arr, l, mid, r);
}
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> tmp = vector<int>(right - left + 1);
int i = left, j = mid + 1;
for(int k = 0;k < tmp.size();k++) {
if (j > right || (i <= mid && arr[i] <= arr[j])) {
tmp[k] = arr[i++];
} else {
tmp[k] = arr[j++];
}
}
for (int k = 0;k < tmp.size();k++) {
arr[left + k] = tmp[k];
}
}