0001 template <typename T> //有序向量(区间)的归并 0002 void Vector<T>::merge ( Rank lo, Rank mi, Rank hi ) { //各自有序的子向量[lo, mi)和[mi, hi) 0003 T* A = _elem + lo; //合并后的向量A[0, hi - lo) = _elem[lo, hi) 0004 int lb = mi - lo; T* B = new T[lb]; //前子向量B[0, lb) = _elem[lo, mi) 0005 for ( Rank i = 0; i < lb; i++ ) B[i] = A[i]; //复制前子向量 0006 int lc = hi - mi; T* C = _elem + mi; //后子向量C[0, lc) = _elem[mi, hi) 0007 for ( Rank i = 0, j = 0, k = 0; j < lb; ) //归并:反复从B和C首元素中取出更小者 0008 A[i++] = ( lc <= k || B[j] <= C[k] ) ? B[j++] : C[k++]; //将其归入A中 0009 delete [] B; //释放临时空间B 0010 }