概述

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是将序列分成两部分，然后用两个指针指向两个序列的开始，比较两个指针所指的值，将较小值放入一个新数组，同时该指针后移。最后将新数组的值赋值给原数组，达到从小到大排列的目的

动画展示

mergeSort.gif

思路解析

  1. 初始序列3 44 38 5 47 15 36 26 27 2 46 4 19 50 48

  2. 这里第一步将序列二分到不能再分，此时左边两个部分为3和44，排序结果作为一个整体为3 44

  3. 然后再处理右边两个部分38和5，排序结果作为一个整体为5 38

  4. 此时在将两个排序好两个整体在进行相同的步骤，每次取较小值，排序结果作为一个整体为3 5 38 44

  5. 同理右半边结果为15 26 36 47

  6. 再处理这两个部分，结果为3 5 15 26 36 38 44 47，此时原序列左半边排序完成

  7. 以相同步骤处理原序列右半边，结果为2 4 19 27 46 48 50

  8. 两个指针相比取最小值放入新数组，结果为2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

算法性能

时间复杂度

归并排序的时间复杂度在平均情况、最好情况以及最坏情况下均为O(n log n)，其中n是数组中的元素数量。这是因为归并排序总是将数组分成两半处理，每一层递归深度为log n层，每层需要线性时间n来合并，故总时间为n * log n。这种时间复杂度保证了归并排序对于大规模数据集来说是非常高效的，且性能稳定，不依赖于原始数据的排列状态。

空间复杂度

归并排序的空间复杂度为O(n)，主要原因是需要一个与原数组相同大小的临时数组来合并两个子数组。这是归并排序的一个缺点，尤其是在处理极大规模数据时，额外的空间需求可能成为一个限制因素。

稳定性

归并排序是一种稳定的排序算法，即相等的元素在排序前后相对位置不变。这是因为合并过程中，当遇到两个相等的元素时，总是先取左边子数组的元素，保持了稳定性。

代码实现

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
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>

using namespace std;

//参数：数组，左边界，右边界(左闭右闭区间)
void merge_sort(vector<int>& v, int l, int r) {
	//结束条件
	if (l >= r)return;
	//得到中间下标
	int mid = (l + r) >> 1;
	//递归执行直到满足结束条件
	merge_sort(v, l, mid);
	merge_sort(v, mid + 1, r);
	//临时数组
	vector<int>temp;
	//声明双指针
	int i = l, j = mid + 1;
	//将较小值push到临时数组
	while (i <= mid && j <= r)
		temp.push_back(v[i] < v[j] ? v[i++] : v[j++]);
	while (i <= mid) temp.push_back(v[i++]);
	while (j <= r) temp.push_back(v[j++]);
	//将临时数组的值赋值到原数组
	for (int i = l, j = 0; i <= r; i++)
		v[i] = temp[j++];
}

int main() {
	vector<int> v = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	merge_sort(v, 0, v.size() - 1);
	for (const auto value : v)
		cout << value << ' ';
	cout << endl;
	return 0;
}