归并排序

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

[c language=”++”]
#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;
}

[/c]