排序之归并排序

归并排序

二路归并属于迭代式算法。每步迭代中，只需比较两个待归并向量的首元素，将小者取出并追加到输出向量的末尾，该元素在原向量中的后继则成为新的首元素。如此往复，直到某一向量为空。最后，将另一非空的向量整体接至输出向量的末尾。

void mergeSort(int* arr, int lo, int hi)
{
	if (hi - lo > 1);
	mergeSort(arr, lo, mi);  mergeSort(arr, mi, hi);
	merge(arr, lo, mi, hi);
}
void merge(int* arr, int lo, int mi, int hi)
{
	int p1 = lo;
	int p2 = mi;
	int* temp = new int[hi - lo];
	int i = 0;
	while ((p1