思想

归并排序（merge sort）是建立在归并操作上的一种有效的排序算法,它以 O(nlogn) 最坏情形运行时间运行。它是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列：即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序可并行实现。

归并排序示例图如下：

实现

合并操作

基本的合并算法是取两个输入数组 A 和 B、一个输出数组 C，以及三个计数器 Aptr， Bptr， Cptr。它们初始置于对应数组的开始端。A[Aptr]和 B[Bptr]中的较小者被拷贝到 C 中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完时，则将另一个表中剩余部分拷贝到 C 中。

如果对 Merge 的每个递归调用均局部声明一个临时数组，那么在任一时刻就可能有 log N 个临时数组处在活动期，这对于小内存机器是致命的。另一方面，如果 Merge 例程动态分配并释放最小量临时内存，那么由 malloc 占用的时间会很多。因此，可将输入数组分成两个输入数组。

/***    @description 对数组a的 a[leftPos, rightPos - 1] 和 a[rightPos, rightEnd] 两部分进行合并操作，结果暂存到tmpArray中，最后拷贝回数组a。*/void Merge(ElementType a[], ElementType tmpArray[], int leftPos, int rightPos, int rightEnd){    int i, leftEnd, numOfElements, tmpPos;     leftEnd = rightPos - 1;    tmpPos = leftPos;    numOfElements = rightEnd - leftPos + 1;            //main loop    while (leftPos <= leftEnd && rightPos <= rightEnd)        if (a[leftPos] < a[rightPos])            tmpArray[tmpPos++] = a[leftPos++];        else            tmpArray[tmpPos++] = a[rightPos++];     //get rest of first half    while (leftPos <= leftEnd)        tmpArray[tmpPos++] = a[leftPos++];     //get rest of second half    while (rightPos <= rightEnd)        tmpArray[tmpPos++] = a[rightPos++];     //copy tmpArray back    for (i = 0; i < numOfElements; ++i, rightEnd--)        a[rightEnd] = tmpArray[rightEnd];}

归并排序

/***    @description 归并排序主算法，对数组a[left, right] 进行归并排序，使用到了暂存数组tmpArray。*/void MSort(ElementType a[], ElementType tmpArray[], int left, int right){    int center;     if (left < right)    {        center = (left + right) / 2;        MSort(a, tmpArray, left, center);        MSort(a, tmpArray, center + 1, right);        Merge(a, tmpArray, left, center + 1, right);    }}

算法主体

/***    @description 归并排序算法，封装了开辟临时存储空间的操作。*/void MergeSort(ElementType a[], int n){    ElementType *tmpArray;     tmpArray = (ElementType *)malloc(sizeof(ElementType) * n);    if (tmpArray != NULL)    {        MSort(a, tmpArray, 0, n - 1);        free(tmpArray);    }    else        puts("No space of tmp Array!");}