归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ1）划分子表
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ2）合并半子表
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ首先我们来讨论归并算法，归并算法将一系列数据放到一个向量中，索引范围为[first,last],这个序列由两个排好序的子表构成，以索引终点（mid）为分界线，以下面一个序列为例
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ7，10，19，25，12，17，21，30，48
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ这样的一个序列中，分为两个子序列 7,10,19,25 和 12,17,21,30,48，如下图所示：
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ再使用归并算法的时候的步骤如下：
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ第一步：比较v[indexA]=7和v[indexB]=12,将较小的v[indexA]取出来放到临时向量tempArray中，然后indexA加1
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ第二步：比较v[indexA]=10和v[indexB]=12,将较小的10放到临时变量tempArray中，然后indexA++;
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ第三步：比较v[indexA]=19与v[indexB]=12，将较小的12存放到临时变量tempArray中，然后indexB++;
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ第四步到第七步：按照以上规则，进行比对和存储，得到如下结果：
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ最后一步：将子表b中剩余项添加到临时向量tempArray中
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ然后将临时变量中的值按照索引位置，拷贝回向量v中，就完成了对向量v的归并排序
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ算法函数为：
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔpublic void Merger(int[] v, int first, int mid, int last)
{
Queue<int> tempV = new Queue<int>();
int indexA, indexB;
//设置indexA，并扫描subArray1 [first,mid]
//设置indexB,并扫描subArray2 [mid,last]
indexA = first;
indexB = mid;
//在没有比较完两个子标的情况下，比较 v[indexA]和v[indexB]
//将其中小的放到临时变量tempV中
while (indexA < mid && indexB < last)
{
if (v[indexA] < v[indexB])
{
tempV.Enqueue(v[indexA]);
indexA++;
}
else
{
tempV.Enqueue(v[indexB]);
indexB++;
}
}
//复制没有比较完子表中的元素
while (indexA < mid)
{
tempV.Enqueue(v[indexA]);
indexA++;
}
while (indexB < last)
{
tempV.Enqueue(v[indexB]);
indexB++;
}
int index = 0;
while (tempV.Count > 0)
{
v[first + index] = tempV.Dequeue();
index++;
}
}
实现归并排序；归并排序算法分为两步，第一步：先将原来的数据表分成排好序的子表，然后调用 Merger 对子表进行归并，使之成为有序表，例如有如下向量：
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ25，10，7，19，3，48，12，17，56，30，21
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ对此序列进行归并排序的步骤为：
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ归并算法函数为
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
public void MergerSort(int[] v, int first, int last)
...{
if (first + 1 < last)
...{
int mid = (first + last) / 2;
MergerSort(v, first, mid);
MergerSort(v, mid, last);
Merger(v, first, mid, last);
}
}归并算法的划分子表和归并子表与原数据序列次序无关，因此算法的最坏情况，最坏情况和平均情况时间复杂度是一样的
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ下面是归并算法的函数调用图
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ示例程序：
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔhttp://files.cnblogs.com/jillzhang/mergersort.rar QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔQAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ人老了，脑袋不好用了，偶尔用算法来练练脑子，可以防止早衰。呵呵
QAY ßMpCJbbs.szblogs.comôïÀ¶f1ÙÔ
