0001 template <typename T> //有序向量(区间)的归并 0002 void Vector<T>::merge ( Rank lo, Rank mi, Rank hi ) { //[lo, mi)和[mi, hi)各自有序,lo < mi < hi 0003 Rank i = 0; T* A = _elem + lo; //合并后的有序向量A[0, hi - lo) = _elem[lo, hi),就地 0004 Rank j = 0, 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]; //复制自A的前缀 0006 Rank k = 0, lc = hi - mi; T* C = _elem + mi; //后子向量C[0, lc) = _elem[mi, hi),就地 0007 while ( ( j < lb ) && ( k < lc ) ) //反复地比较B、C的首元素 0008 A[i++] = ( B[j] <= C[k] ) ? B[j++] : C[k++]; //将更小者归入A中 0009 while ( j < lb ) //若C先耗尽,则 0010 A[i++] = B[j++]; //将B残余的后缀归入A中——若B先耗尽呢? 0011 delete [] B; //释放临时空间:mergeSort()过程中,如何避免此类反复的new/delete? 0012 }