归并排序-非递归算法C++

template 
void merge(vector& a, vector& tempArray, int leftPos, int rightPos, int rightEnd)
{
	int leftEnd = rightPos - 1;
	int numElements = rightEnd - leftPos + 1;
	int tempPos = leftPos;
	while (leftPos <= leftEnd && rightPos <= rightEnd)
	{
		if (a[leftPos] <= a[rightPos])
		{
			tempArray[tempPos++] = std::move(a[leftPos++]);
		}
		else
		{
			tempArray[tempPos++] = std::move(a[rightPos++]);
		}
	}
	while (leftPos <= leftEnd)
	{
		tempArray[tempPos++] = std::move(a[leftPos++]);
	}
	while (rightPos <= rightEnd)
	{
		tempArray[tempPos++] = std::move(a[rightPos++]);
	}
	for (int i = rightEnd; numElements > 0; numElements--, i--)
	{
		a[i] = std::move(tempArray[i]);
	}
}


template 
void mergeSort(vector& a)
{
	vector tempArray(a.size());
	int n = a.size();
	for (int subListSize = 1; subListSize < n; subListSize *= 2) //初始表的大小为1，后续为2， 4， 8，直到只有两个子表
	{
		int leftPos = 0;
		while (leftPos + subListSize <= n - 1) //循环将每两个子表合并为一个有序表。
		{
			int rightPos = leftPos + subListSize;
			int rightEnd = std::min(n - 1, rightPos + subListSize - 1);
			merge(a, tempArray, leftPos, rightPos, rightEnd);
			leftPos = rightEnd + 1;
		}
	}
}