归并排序

需要借助一个数组，时间复杂度为O(nlogn)，空间复杂度为O(n)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
using namespace std;

void Merge(vector<int>&arr, vector<int>&tmp, int l, int k, int r)
{
	int i = l;
	int j = k + 1;
	int p = l;

	while (i <= k&&j <= r)
	{
		if (arr[i] < arr[j])
			tmp[p++] = arr[i++];
		else
			tmp[p++] = arr[j++];
	}

	while (i <= k)
		tmp[p++] = arr[i++];

	while (j <= r)
		tmp[p++] = arr[j++];

	for (i = l; i <= r; ++i)
		arr[i] = tmp[i];
}

void MSort(vector<int>&arr, vector<int>&tmp, int l, int r)
{
	if (l >= r) return;
	int k = (l + r) / 2;
	MSort(arr, tmp, l, k);
	MSort(arr, tmp, k + 1, r);
	Merge(arr, tmp, l, k, r);
}

void MergeSort(vector<int>&arr)
{
	vector<int> tmp(arr.size());
	MSort(arr, tmp, 0, arr.size() - 1);
}
int main()
{
	vector<int> arr = { 12,1 , 123, 1, 4, 2, 54, 3, 52, 3, 12, 4, 123,55 , 135 };
	MergeSort(arr);

	return 0;
}