归并排序

#include<iostream>
#include<vector>
using namespace std;

//将两个排好序的序列合并
void merge(vector<int>& data, int start, int mid, int end)
{
	vector<int> tmp(end - start + 1);
	int i = start;            // 第1个有序区的索引
	int j = mid + 1;        // 第2个有序区的索引
	int k = 0;                // 临时区域的索引

	while (i <= mid && j <= end)
	{
		if (data[i] <= data[j])
			tmp[k++] = data[i++];
		else
			tmp[k++] = data[j++];
	}

	while (i <= mid)
		tmp[k++] = data[i++];

	while (j <= end)
		tmp[k++] = data[j++];

	for (i = 0; i < tmp.size(); i++)
		data[start + i] = tmp[i];
}

//分开序列
void merge_sort_up2down(vector<int>& data, int start, int end)
{
	if (data.size() == 0 || start >= end)
		return;

	int mid = (start + end) / 2;
	merge_sort_up2down(data, start, mid);
	merge_sort_up2down(data, mid + 1, end);

	merge(data, start, mid, end);
}


int main()
{
	vector<int> data = { 80, 30, 60, 40, 20, 10, 50, 70 };
	
	cout << "before sort:";
	for (size_t i = 0; i < data.size(); i++)
	{
		cout << data[i] << " ";
	}
	cout << endl;

	merge_sort_up2down(data, 0, data.size() - 1);//归并排序

	cout << "after  sort:";
	for (size_t i = 0; i < data.size(); i++)
	{
		cout << data[i] << " ";
	}
	cout << endl;

	getchar();
	return 0;
}