排序算法：归并排序

递归实现

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 p = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[p++] = arr[begin1++];
		}
		else
		{
			tmp[p++] = arr[begin2++];
		}
	}
	while(begin1 <= end1)
		tmp[p++] = arr[begin1++];
	while (begin2 <= end2)
	{
		tmp[p++] = arr[begin2++];
	}
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}
void MergeSort(int* arr, int sz)
{
	int* tmp = (int*)malloc(sizeof(int) * sz);
	_MergeSort(arr, 0, sz - 1, tmp);
	free(tmp);
}

非递归实现

void MergeSort(int* arr, int sz)
{
	int* tmp = (int*)malloc(sizeof(int) * sz);
	int gap = 1;
	while (gap < sz)
	{
		for (int i = 0; i < sz; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = begin1 + gap - 1;
			int begin2 = end1 + 1;
			int end2 = begin2 + gap - 1;
			int index = begin1;
			if (end1 >= sz)
				end1 = sz - 1;
            
			// begin2 越界，第二个区间不存在
			if (begin2 >= sz)
			{
				begin2 = sz;
				end2 = sz - 1;
			}
			// begin2 ok， end2越界，修正end2即可
			if (begin2 < sz && end2 >= sz)
				end2 = sz - 1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
					tmp[index++] = arr[begin1++];
				else
					tmp[index++] = arr[begin2++];
			}
			while(begin1 <= end1)
				tmp[index++] = arr[begin1++];
			while(begin2 <= end2)
				tmp[index++] = arr[begin2++];
			for (int j = i; j < index; j++)
			{
				arr[j] = tmp[j];
			}
		}
		//memcpy(arr, tmp, sizeof(int) * sz);//copy到arr也可以直接这样
		gap *= 2;
	}
    free(tmp);
}

归并排序可以实现外排序。