(2)具体算法

　　[cpp]

　　void MergeSortDC(SeqList R，int low，int high)

　　{//用分治法对R[low..high]进行二路归并排序

　　int mid;

　　if(low

　　mid=(low+high)/2; //分解

　　MergeSortDC(R，low，mid); //递归地对R[low..mid]排序

　　MergeSortDC(R，mid+1，high); //递归地对R[mid+1..high]排序

　　Merge(R，low，mid，high); //组合，将两个有序区归并为一个有序区

　　}

　　}//MergeSortDC

　　void MergeSortDC(SeqList R，int low，int high)

　　{//用分治法对R[low..high]进行二路归并排序

　　int mid;

　　if(low

　　mid=(low+high)/2; //分解

　　MergeSortDC(R，low，mid); //递归地对R[low..mid]排序

　　MergeSortDC(R，mid+1，high); //递归地对R[mid+1..high]排序

　　Merge(R，low，mid，high); //组合，将两个有序区归并为一个有序区

　　}

　　}//MergeSortDC

　　(3)算法MergeSortDC的执行过程

　　算法MergeSortDC的执行过程如下图所示的递归树。

　　归并排序示例： 自顶向下的二路归并的执行过程

　　三 算法整体过程演示

　　一个归并排序的例子:对一个随机点的链表进行排序：

　　四 算法性能分析

　　1、稳定性

　　归并排序是一种稳定的排序。

　　2、存储结构要求

　　可用顺序存储结构。也易于在链表上实现。

　　3、时间复杂度

　　对长度为n的文件，需进行 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

　　4、空间复杂度

　　需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。