//subMerge2----非哨兵方法实现两个有序序列的合并 template
     
       void subMerge2(vector
      
        &array,                          typename vector
       
        ::iterator iterBegin,                          typename vector
        
         ::iterator iterBarrier,                          typename vector
         
          ::iterator iterEnd) {
   //创建两个数组，分别存放以iterBarrier为界线的array的左边部分和右边部分     vector
          
            arrayLeft(iterBegin, iterBarrier+1); vector
           
             arrayRight(iterBarrier+1, iterEnd); //定义分别指向两个数组的迭代器 typename vector
            
             ::iterator iterLeft = arrayLeft.begin(); typename vector
             
              ::iterator iterRight = arrayRight.begin(); //定义指向原数组array的迭代器 typename vector
              
               ::iterator iterArray = iterBegin; //只要其中一个数组为空则跳出循环 while(iterLeft!=arrayLeft.end() && iterRight!=arrayRight.end()) { if(*iterLeft < *iterRight) //如果左边小，将左边的值放入原数组 { *iterArray = *iterLeft; ++iterLeft; ++iterArray; } else //如果右边小，将右边的值放入原数组 { *iterArray = *iterRight; ++iterRight; ++iterArray; } } //左边为空 if(iterLeft==arrayLeft.end()) { //将右边剩下的数据复制到原数组 //array.erase(iterArray, iterEnd); //array.insert(iterArray, iterRight, arrayRight.end()); while(iterRight != arrayRight.end()) { *iterArray = *iterRight; ++iterRight; ++iterArray; } } //右边为空 if(iterRight==arrayRight.end()) { //将左边剩下数据复制到原数组 //array.erase(iterArray, iterEnd); //array.insert(iterArray, iterLeft, arrayLeft.end()); while(iterLeft != arrayLeft.end()) { *iterArray = *iterLeft; ++iterLeft; ++iterArray; } } return; }
              
             
            
           
          
         
        
       
      
     

用此函数代替之前mergeSort()中的 subMerge即可。其中在将左边或右边剩余元素复制到原数组的时候，如果用 vector成员函数insert，

必须先将iterArray所指位置右边的元素删除，不然会使iterArray右边的元素向后移动，导致元素个数增多。