typedef struct _DLINK DLINK;
struct _DLINK{
    DLINK *pNext, *pPrev;
};

typedef struct _DLIST{
	UINTN Size;
	DLINK *pHead, *pTail;
} DLIST;

VOID SortList(DLIST *List,  COMPARE_FUNCTION Compare){
    DLIST MergeList;
    DLINK *p, *q, *e;
    UINTN pSize, qSize, inSize;
    UINT32 NoMerges;
    UINTN i;

    if(List->Size <= 1)  //nothing to sort
        return;

    inSize = 1;
    MergeList = *List;

    while(1)
    {
        p = MergeList.pHead;
        DListInit(&MergeList);      //clear list  DlistInit()是把链表初始化为空，没有节点
        NoMerges = 0;

        while(p != NULL)
        {
            NoMerges++;
            q = p;
            for(i = 0, pSize = 0; i < inSize; i++)
            {
                pSize++;
                q = q->pNext;
                if(q == NULL)
                    break;
            }

            qSize = inSize;
            while(pSize > 0 || (qSize > 0 && q != NULL))
            {
               if(pSize == 0)
                {
                    e = q;
                    q = q->pNext;
                    DListAdd(&MergeList, e);
                    qSize--;
                }
                else if(qSize == 0 || q == NULL)
                {
                    e = p;
                    p = p->pNext;
                    DListAdd(&MergeList, e);     //DListAdd() 是把节点e添加到链表MergeList末尾
                    pSize--;
                }
                else if(Compare(p, q) > 0)       //compare() 比较节点p，q的大小
                {
                    e = q;
                    q = q->pNext;
                    DListAdd(&MergeList, e);
                    qSize--;
                }
                else
                {
                    e = p;
                    p = p->pNext;
                    DListAdd(&MergeList, e);
                    pSize--;
                }
            }
            p = q;
        }
        if(NoMerges <= 1)
            break;
        inSize *= 2;
    }
    *List = MergeList;
}

[峰会]看雪.第八届安全开发者峰会10月23日上海龙之梦大酒店举办！