归并排序（C++实现）

#include
using namespace std;

void Merge(int* p, const int& pos1, const int& pos2, const int& pos3)
{
	int Length1 = pos2 - pos1 + 1;
	int* tp = new int[Length1];
	for (int i = 0; i < Length1; i++)
	{
		tp[i] = p[i + pos1];
	}
	int i = pos1, j = pos2 + 1, k = pos1;
	for (; i <= pos2 && j <= pos3; k++)
	{
		if (tp[i-pos1] <= p[j])
		{
			p[k] = tp[i-pos1];
			i++;
		}
		else p[k] = p[j++];
	}
	if (i > pos2)
	{
		for (; j <= pos3; j++, k++)
		{
			p[k] = p[j];
		}
	}
	if (j > pos3)
	{
		for (; i <= pos2; i++, k++)
		{
			p[k] = tp[i-pos1];
		}
	}
}

void MergeSort(int* p, const int& pos1,const int& pos2)
{
	if (pos1 >= pos2)
	{
		return;
	}
	int middle = (pos1 + pos2) >> 1;
	MergeSort(p, pos1, middle);
	MergeSort(p, middle + 1, pos2);
	Merge(p,pos1, middle, pos2);
} 

int main(void)
{
	int n;
	cout << "请输入数组元素的个数：";
	cin >> n;
	int* array = new int[n];
	cout << "请分别输入数组元素：";
	for (int i = 0; i < n; i++)
	{
		cin >> array[i];
	}
	MergeSort(array, 0, n - 1);
	cout << "从小到大排序后的数组为：";
	for (int i = 0; i < n; i++)
	{
		cout << array[i] << " ";
	}
	cout << endl;
	return 0;
}