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

}</pre>