归并排序算法：
/* 归并排序，算法时间复杂度为：O(nlogn)， 稳定排序算法 Written by： Qinchao Time：2016/12/3 Language： C++ */ const int INFTY = 2147483647; void merge(vector<int> &_num, int left, int mid, int right ) { int n1 = mid - left + 1; int n2 = right - mid; vector<int> L(n1+1); for (int i = 0; i < n1; i++) L[i] = _num[left+i]; L[n1] = INFTY;//无穷数 vector<int> R(n2+1); for (int i = 0; i < n2; i++) R[i] = _num[mid+i+1]; R[n2] = INFTY;//无穷数 int i = 0, j = 0; for (int k = left; k <= right; k++) { if (L[i] <= R[j]) { _num[k] = L[i]; i++; } else { _num[k] = R[j]; j++; } } } void mergesort_9(vector<int> &_snum, int sleft, int sright) { if (sleft < sright) { int q = (sleft + sright) / 2; mergesort_9(_snum, sleft, q); mergesort_9(_snum, q + 1, sright); merge(_snum, sleft, q, sright); } }