/* * mergeSort.cpp *  合并排序算法，算法导论P.17 *  Created on: 2011-12-21 *      Author: LiChanghai *///#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define FLT_MAX 1.0E38 //定义一个很大的值作为哨兵//对于待排序的数组 A[p...r], 其子数组A[p...q]，A[q+1...r]已排好序//函数 subMerge(A, p, q, r), 将两个已排好序的子数组A[p...q]，A[q+1...r]//合并成一个有序的数组代替当前的数组A[p...r]template
         
          void subMerge(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); //在两个数组尾部分别放一个“哨兵” T temp = T(FLT_MAX); arrayLeft.push_back(temp); arrayRight.push_back(temp); //定义分别指向两个数组的迭代器 typename vector
                
                 ::iterator iterLeft = arrayLeft.begin(); typename vector
                 
                  ::iterator iterRight = arrayRight.begin(); //定义指向原数组array的迭代器 typename vector
                  
                   ::iterator iterArray = iterBegin; for(; iterArray != iterEnd; ++iterArray) if(*iterLeft < *iterRight) //如果左边小，将左边的值放入原数组 { *iterArray = *iterLeft; ++iterLeft; } else //如果右边小，将右边的值放入原数组 { *iterArray = *iterRight; ++iterRight; } return;}//函数 mergeSort(A, p, r) 调用subMerge对任意数组排序，p, r为下标//mergeSort(A, p, r)首先将数组A分为两部分//然后递归调用其本身对这两部分 分别排序//依次递归下去，直到只剩2个数的时候完成这两个数的排序//然后再层层返回调用处，将已排好序的子序列合并成更大的有序序列//最后一次调用subMerge时完成数组的排序template
                   
                    void mergeSort(vector
                    
                      &vec, typename vector
                     
                      ::iterator iterHead, typename vector
                      
                       ::iterator iterTail){ //测试 mergeSort 调用了多少次 //static int times_mergeSort=0; //cout<<"the "<<++times_mergeSort<<" call mergeSort()"<
                       
                        ::size_type halfLength = (vec.size()-1)/2; //数组长度的一半（正确方法） typename vector
                        
                         ::difference_type halfLength=( (iterTail-iterHead)-1)/2; //定义一个迭代器指向数组 vec 中间位置 typename vector
                         
                          ::iterator iterDivide = iterHead + halfLength; mergeSort(vec, iterHead, iterDivide+1); //递归调用自身对前半段排序 mergeSort(vec, iterDivide+1, iterTail); //递归调用自身对后半段排序 //cout<<"the "<<++times_subMerge<<" call subMerge()"<