双向链接列表-合并排序后更新列表->尾

您的算法通过对merge函数的每一步进行递归来使用O（N）堆栈空间。使用这种方法，跟踪tail节点将非常麻烦。您只需扫描列表即可找到它并更新中的list结构linklist_sort。这个额外的步骤不会改变分类操作的复杂性。您可以通过从：的当前值开始节省一些时间，link->tail如果列表已经排序，循环将立即停止。

这是修改后的版本：

void linklist_sort(struct linklist *list, int (*comp)(const void *, const void *)) {
    list->head = merge_sort(list->head, comp);
    if (list->tail) {
        struct node *tail = list->tail;
        while (tail->next)
            tail = tail->next;
        list->tail = tail;
    }
}

使用合并排序对链表进行排序仅应使用O（log（N））空间和O（N log（N））时间。

以下是一些改进此算法的想法：

• 由于您知道列表的长度，因此无需扫描整个列表进行拆分。您可以将长度与列表指针一起传递，并使用它来确定在何处进行拆分，并仅扫描列表的一半。

• 如果转换merge为非递归版本，则可以跟踪合并阶段中的最后一个节点，并更新struct node **tailp作为参数传递的指针以指向该最后一个节点。这将保存上一次扫描，并且删除递归将降低空间复杂度。基准测试可以证明这是否会提高效率尚不清楚。

• 根据经验，使用指向列表节点的N个指针的辅助数组，可以更有效地实现对链接列表的单独排序和双重链接的排序。您将对该数组进行排序，然后根据排序后的数组的顺序重新链接节点。额外的要求是O（N）大小。

这是使用列表长度和非递归的修改版本merge：

struct node {
    void *data;
    struct node *prev;
    struct node *next;
};

struct linklist {
    struct node *head;
    struct node *tail;
    size_t size;
};

static struct node *split(struct node *head, size_t pos) {
    struct node *slow = head;

    while (pos-- > 1) {
        slow = slow->next;
    }
    struct node *temp = slow->next;
    slow->next = NULL;
    return temp;
}

static struct node *merge(struct node *first, struct node *second,
                          int (*comp)(const void *, const void *))
{
    struct node *head = NULL;
    struct node *prev = NULL;
    struct node **linkp = &head;

    for (;;) {
        if (first == NULL) {
            second->prev = prev;
            *linkp = second;
            break;
        }
        if (second == NULL) {
            first->prev = prev;
            *linkp = first;
            break;
        }
        if (comp(first->data, second->data)) <= 0 {
            first->prev = prev;
            prev = *linkp = first;
            linkp = &first->next;
        } else {
            second->prev = prev;
            prev = *linkp = second;
            linkp = &second->next;
        }
    }
    return head;
}

static struct node *merge_sort(struct node *head, size_t size,
                               int (*comp)(const void *, const void *))
{
    if (size < 2) {
        return head;
    }

    struct node *second = split(head, size / 2);

    head = merge_sort(head, size / 2, comp);
    second = merge_sort(second, size - size / 2, comp);
    return merge(head, second, comp);
}

void linklist_sort(struct linklist *list, int (*comp)(const void *, const void *)) {
    list->head = merge_sort(list->head, comp, list->size);
    if (list->tail) {
        struct node *tail = list->tail;
        while (tail->next)
            tail = tail->next;
        list->tail = tail;
    }
}

请注意，您还可以简化merge功能，并且在排序期间不更新后退指针，因为您可以在上一次扫描期间重新链接整个列表。最后一次扫描将更长且对缓存的友好程度较低，但仍应更高效且更不易出错。