0001 template <typename T> //列表的归并排序算法:对起始于位置p的n个元素排序 0002 void List<T>::mergeSort ( ListNodePosi(T) & p, int n ) { //valid(p) && rank(p) + n <= size 0003 if ( n < 2 ) return; //若待排序范围已足够小,则直接返回;否则... 0004 int m = n >> 1; //以中点为界 0005 ListNodePosi(T) q = p; for ( int i = 0; i < m; i++ ) q = q->succ; //均分列表 0006 mergeSort ( p, m ); mergeSort ( q, n - m ); //对前、后子列表分别排序 0007 merge ( p, m, *this, q, n - m ); //归并 0008 } //注意:排序后,p依然指向归并后区间的(新)起点