合并排序（非哨兵方法）

//subMerge2----非哨兵方法实现两个有序序列的合并
template
void subMerge2(vector &array,
typename vector::iterator iterBegin,
typename vector::iterator iterBarrier,
typename vector::iterator iterEnd)
{
//创建两个数组&＃xff0c;分别存放以iterBarrier为界线的array的左边部分和右边部分
vector arrayLeft(iterBegin, iterBarrier&＃43;1);
vector arrayRight(iterBarrier&＃43;1, iterEnd);

//定义分别指向两个数组的迭代器
typename vector::iterator iterLeft &＃61; arrayLeft.begin();
typename vector::iterator iterRight &＃61; arrayRight.begin();

//定义指向原数组array的迭代器
typename vector::iterator iterArray &＃61; iterBegin;

//只要其中一个数组为空则跳出循环
while(iterLeft!&＃61;arrayLeft.end() && iterRight!&＃61;arrayRight.end())
{
if(*iterLeft <*iterRight) //如果左边小&＃xff0c;将左边的值放入原数组
{
*iterArray &＃61; *iterLeft;
&＃43;&＃43;iterLeft;
&＃43;&＃43;iterArray;
}
else //如果右边小&＃xff0c;将右边的值放入原数组
{
*iterArray &＃61; *iterRight;
&＃43;&＃43;iterRight;
&＃43;&＃43;iterArray;
}
}
//左边为空
if(iterLeft&＃61;&＃61;arrayLeft.end())
{
//将右边剩下的数据复制到原数组
//array.erase(iterArray, iterEnd);
//array.insert(iterArray, iterRight, arrayRight.end());
while(iterRight !&＃61; arrayRight.end())
{
*iterArray &＃61; *iterRight;
&＃43;&＃43;iterRight;
&＃43;&＃43;iterArray;
}
}
//右边为空
if(iterRight&＃61;&＃61;arrayRight.end())
{
//将左边剩下数据复制到原数组
//array.erase(iterArray, iterEnd);
//array.insert(iterArray, iterLeft, arrayLeft.end());
while(iterLeft !&＃61; arrayLeft.end())
{
*iterArray &＃61; *iterLeft;
&＃43;&＃43;iterLeft;
&＃43;&＃43;iterArray;
}
}
return;
}