归并排序

void merge(int *arr, int left, int mid, int right)
{
	int *tmparr = new int[right - left + 1];
	int leftindex = left, rightindex = mid + 1;
	int tmpindex = 0;
	while (leftindex <= mid && rightindex <= right)
	{
		if (arr[leftindex] < arr[rightindex])
			tmparr[tmpindex++] = arr[leftindex++];
		else
			tmparr[tmpindex++] = arr[rightindex++];
	}
	while (leftindex <= mid)
		tmparr[tmpindex++] = arr[leftindex++];
	while (rightindex <= right)
		tmparr[tmpindex++] = arr[rightindex++];
	tmpindex = 0;
	while (left <= right)
		arr[left++] = tmparr[tmpindex++];
}

void mergesort_nonerecursive(int *arr, int left, int right)
{
	int step = 2, i = 0;
	while (step <= right + 1)
	{
		i = 0;
		while (i + step <= right)
		{
			merge(arr, i, i + step / 2 - 1, i + step - 1);
			i += step;
		}
		merge(arr, i, i + step / 2 - 1, right);
		step *= 2;
	}
	merge(arr, 0, step / 2 - 1, right);
}