归并排序

归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

第一个问题，解决 合并两个有序数组。
这个问题比较简单，把两个有序数组看着两个顺序栈，比较栈顶元素，将较小者弹出到新的队列中；然后再次比较栈顶元素，如此重复。直到一个数组元素全部完毕，那么剩余数组的元素一次添加到新队列的尾部，即完成合并。
实现如下：

static void mergeList(int listA[], int lenA, int listB[], int lenB, int outList[])
{
    int idxa = 0;
    int idxb = 0;
    int idxout = 0;
    int i;

    while (idxa < lenA && idxb < lenB)
    {
        if (listA[idxa] <= listB[idxb])
            outList[idxout++] = listA[idxa++];
        else
            outList[idxout++] = listB[idxb++];
    }

    if (idxa < lenA)
    {
        for (i = idxa; i < lenA; i++)
            outList[idxout++] = listA[idxa];
    }

    if (idxb < lenB)
    {
        for (i = idxb; i < lenB; i++)
            outList[idxout++] = listB[idxb];
    }
}

基于上面的分析和实现，归并排序的算法实现：
（1）以步长为1（相邻元素），进行有序合并；合并后，每两个元素满足有序关系；
（2） 按2的倍数增大步长，同样进行相邻组有序合并，直到步长大于/等于 (len + 1)/2，此时完成了最后一次将整个数组分为两个有序数组的合并。即完成了排序。
实现如下：

void DACsort(int list[], int len)
{
    int grpLen = 1;
    int grpLeft; // left group start index
    int grpLftLen;
    int grpRtLen;
    int i;

    int *pConter;
    int *pCur;
    int *pBk;
    int *pTemp;
    int *pMerge;

    // 辅助队列，与原始数据队列交替使用
    pConter = (int *)malloc(sizeof(int) * len);
    if (NULL == pConter)
        return;
    pBk = list;
    pCur = pConter;

    while(grpLen <= (len + 1) / 2)
    {
        pMerge = pCur;
        for (grpLeft = 0; grpLeft < len; grpLeft += grpLen * 2)
        {
            if (grpLeft + grpLen < len)
            {
                grpLftLen = grpLen;

                if (grpLeft + 2 *grpLen <= len)
                    grpRtLen = grpLen;
                else
                    grpRtLen = len - (grpLeft + grpLen);
            }
            else
            {
                grpLftLen = len - grpLeft;
                grpRtLen = 0;
            }

            mergeList(pBk + grpLeft, grpLftLen, pBk + grpLeft + grpLen, grpRtLen, pMerge);
            pMerge += grpLftLen + grpRtLen;
        }

        pTemp = pBk;
        pBk = pCur;
        pCur = pTemp;
        grpLen *= 2;
    }

    if (pBk != list)
    {
        for (i = 0; i < len; i++)
            list[i] = pBk[i];
    }
    free(pConter);
}