排序算法总结

归并排序是一个基于分治的算法。

时间复杂度 $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];
    }
}