归并排序

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

void mergeSort(int* arr, int lo, int hi) { 	if (hi - lo < 2) return;//一个元素时就可以不分了 	int mi = lo + ((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 < mi) && (p2 < hi )) { 		if (arr[p1] < arr[p2]) { 			temp[i++] = arr[p1++]; 		} 		else { 			temp[i++] = arr[p2++]; 		} 	} 	while (p1 < mi) { 		temp[i++] = arr[p1++]; 	} 	while (p2 < hi) { 		temp[i++] = arr[p2++]; 	} 	for (int j = 0; j < hi - lo; j++) 		arr[lo + j] = temp[j]; 	delete[] temp; }