归并排序 - 分治与倍增 - 深入浅出程序设计竞赛(进阶篇) - 书籍

归并排序（Merge Sort）是一种常见的排序算法，基于分治策略。它将待排序的数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个有序的数组。

归并排序的基本思想如下：

下面是一个使用 C++ 实现的归并排序的示例代码：

	#include <iostream>
	#include <vector>
	using namespace std;

	void merge(vector<int>& nums, int left, int mid, int right) {
	int n1 = mid - left + 1;
	int n2 = right - mid;

	vector<int> L(n1);
	vector<int> R(n2);

	for (int i = 0; i < n1; ++i) {
	L[i] = nums[left + i];
	}

	for (int j = 0; j < n2; ++j) {
	R[j] = nums[mid + 1 + j];
	}

	int i = 0, j = 0, k = left;
	while (i < n1 && j < n2) {
	if (L[i] <= R[j]) {
	nums[k] = L[i];
	++i;
	} else {
	nums[k] = R[j];
	++j;
	}
	++k;
	}

	while (i < n1) {
	nums[k] = L[i];
	++i;
	++k;
	}

	while (j < n2) {
	nums[k] = R[j];
	++j;
	++k;
	}
	}

	void mergeSort(vector<int>& nums, int left, int right) {
	if (left < right) {
	int mid = left + (right - left) / 2;

	mergeSort(nums, left, mid);
	mergeSort(nums, mid + 1, right);

	merge(nums, left, mid, right);
	}
	}

	int main() {
	vector<int> nums = {4, 2, 7, 5, 1, 6, 3};

	mergeSort(nums, 0, nums.size() - 1);

	for (int num : nums) {
	cout << num << " ";
	}
	cout << endl;

	return 0;
	}

在这个例子中，我们使用了递归的方式实现归并排序。 mergeSort 函数用于对数组的指定范围进行排序， merge 函数用于将两个有序的子数组合并成一个有序的数组。

归并排序的时间复杂度为 O (nlogn)，其中 n 表示待排序数组的长度。它是一种稳定的排序算法，适用于各种规模的数据集。由于归并排序需要额外的空间来存储临时数组，在处理大规模数据时可能会占用较多的内存。