/*******************************mergeSort******************************/#include "stdafx.h"#include 
    
     using namespace std;template 
     
      void mergeSort(vector
      
       & vec){	vector
       
         tempVec(vec.size());	mergeSort(vec, tempVec, 0, vec.size()- 1);}template 
        
         void mergeSort(vector
         
          & vec, vector
          
            tempVec, int left, int right){ if (left < right) { int center = (left + right)/2; mergeSort(vec, tempVec, left, center); mergeSort(vec, tempVec, center+1, right); mergeFunc(vec, tempVec, left, center+1 , right);  //合并 }};//合并函数template 
           
            void mergeFunc(vector
            
             & vec, vector
             
               tempVec, int left, int  Pos,int right){ int leftPos = left;          //左边序列的位置，初始为左序列起点 int leftEnd = Pos-1 ;    //左边序列的终点    int rightPos = Pos;           //右边序列的位置，初始为右序列起点 int rightEnd = right; //右边序列的终点 int tempPos = left;         //临时数组的位置，初始为临时数组的起点 int numElements = right - left + 1;          //数组元素的个数 //两段数组合并 //两段数组已有序 while (leftPos <= leftEnd && rightPos <= rightEnd) //左边数组和右边数组都没有到终点 { //比较左边数组和右边数组值的大小 //把较小者放入临时数组 if (vec[leftPos] <= vec[rightPos])            { tempVec[tempPos++] = vec[leftPos++]; } else tempVec[tempPos++] = vec[rightPos++]; } // 只剩一个序列时，直接复制到临时数组 while (leftPos <= leftEnd) { tempVec[tempPos++] = vec[leftPos++]; } while (rightPos <= rightEnd) { tempVec[tempPos++] = vec[rightPos++]; } //将临时数组的值复制回源数组 int i = 0; for (; i< numElements; i++, rightEnd--)  //这里从后向前复制，因为前面有很多垃圾数据 { vec[rightEnd] = tempVec[rightEnd]; }}