归并排序（简单易懂的代码）

归并排序是一种很重要的排序算法，体现的是分而治之的思想，很多的算法题的解法会借用这种算法思想，在这里使用C++编程实现归并排序，供自己回忆，供他人参考~

#include <bits/stdc++.h>
using namespace std;

// 合并(Merge)
void merge(vector<int> &vec, int start, int mid, int end) {
	vector<int> temp;  // 用来保存二路归并的临时结果
	int i = start, j = mid + 1;
	// 二路归并
	while (i <= mid && j <= end) {
		if (vec[i] < vec[j]) {
			temp.push_back(vec[i++]);
		} else {
			temp.push_back(vec[j++]);
		}
	} 
	// 处理剩余的
	while (i <= mid) temp.push_back(vec[i++]);
	while (j <= end) temp.push_back(vec[j++]);
	//重新赋值回去
	for (int k = 0; k < temp.size(); k++) {
		vec[start + k] = temp[k];
	} 
}
 
// mergeSort
void mergeSort(vector<int> &vec, int start, int end) {
	// 递归出口
	if (vec.empty() || start >= end) {
		return;
	}
	// 二分 
	int mid = start + (end - start) / 2;
	// 递归
	mergeSort(vec, start, mid);
	mergeSort(vec, mid + 1, end);
	// 归并
	merge(vec, start, mid, end); 
}

int main() {
	// 初始化一个待排序的向量 
	vector<int> vec = {1, 8, -6, 12, 5, 9};
	// 调用自己写的快排 
	mergeSort(vec, 0, vec.size() - 1);
	// 打印出排序之后的结果 
	for (auto x : vec) {
		cout << x << ",";  // -6,1,5,8,9,12, 
	}
	return 0;
}