归并排序及其应用场景

一、归并排序的概念

二、归并排序递归与非递归实现

归并排序递归实现，分治为每个区间元素都有序，那么就得把区间 分治成为1才能保证区间中每个元素都有序，在归并：

//归并排序
void _MergeSort(int*arr, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	int mid = left + (right - left) / 2;
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	int begin1 = left;
	int end1 = mid;

	int begin2 = mid + 1;
	int end2 = right;

	int i = left; 

	while (begin1