1. 排序

排序算法（Sorting Algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。

除了时空复杂度，我们通常还关心排序算法的稳定性，稳定的排序算法不改变原始数据相等元素的顺序。

1. 归并排序

归并排序（Merge Sort）基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均的情况下均为 O(nlog⁡n)\mathbf{O}(n\log{n})，空间复杂度为 O(n)\mathbf{O}(n)，是一个稳定的排序算法。

归并排序的核心是合并过程，假设一个 std::vector 已经被划分为有序的两个部分：[left,mid)[left, mid) 和 [mid,right)[mid, right)，那我们的合并逻辑可以是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template<typename T>
void merge(std::vector<T>& arr, std::vector<T>& tmp, size_t left, size_t mid, size_t right)
{
	// 合并两个有序区间 [left, mid) 和 [mid, right)
	size_t i = left, j = mid, tmpIdx = left;
	while (i < mid && j < right)
	{
		if (arr[i] <= arr[j]) // 保持稳定性
		{
			tmp[tmpIdx++] = std::move(arr[i++]); // 移动赋值，避免拷贝
		}
		else
		{ 
			tmp[tmpIdx++] = std::move(arr[j++]);
		}
	}
	while (i < mid)
	{
		tmp[tmpIdx++] = std::move(arr[i++]);
	}
	while (j < right)
	{
		tmp[tmpIdx++] = std::move(arr[j++]);
	}
	// 将合并结果复制回原数组
	std::move(tmp.begin() + left, tmp.begin() + right, arr.begin() + left);
}

对于两份正序数据，合并它们只需要同时遍历二者，结果中加入当前较小元素。当其中一份数据遍历完成后，将剩余的另一份数据追加在结果尾部。

上述代码中两种 std::move 的用法并不一样，前者将左值转换为右值引用，以便调用移动构造函数避免拷贝。后者则是将源范围的元素移动到目标范围。

而归并排序的过程可以看作是将源数据划分为两部分，对这两部分分别执行归并排序，再合并的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template<typename T>
void mergeSortImpl(std::vector<T>& arr, std::vector<T>& tmp, size_t left, size_t right) 
{
	if (right - left <= 1)
	{
		return;
	}

	size_t mid = left + (right - left) / 2;
	mergeSortImpl(arr, tmp, left, mid);
	mergeSortImpl(arr, tmp, mid, right);

	merge(arr, tmp, left, mid, right);
}

template<typename T>
void mergeSort(std::vector<T>& arr) 
{
	if (arr.size() <= 1)
	{
		return;
	}

	// 预分配临时数组，避免递归中反复分配
	std::vector<T> temp(arr.size());
	mergeSortImpl(arr, temp, 0, arr.size());
}

二路归并是最常见的写法，如果数据规模巨大，完全可以结合并行技术使用多路归并。

Reference