/******************************
*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];
    }
}