/******************************  *mergeSort  ******************************/  #include "stdafx.h"  #include <vector>  using namespace std;     template <typename T>  void mergeSort(vector<T>& vec)  {      vector<T> tempVec(vec.size());      mergeSort(vec, tempVec, 0, vec.size()- 1);  }     template <typename T>  void mergeSort(vector<T>& vec, vector<T> 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 <typename T>  void mergeFunc(vector<T>& vec, vector<T> 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];      }  }