使用C中的合并排序或快速排序对很长的链接列表进行排序

您的排序代码不正确：您交换了content字段，但没有交换content_size。您应该通过更新列表next成员和更新*head参数来对列表元素进行排序。

如果不差的话，您的方法将具有二次复杂度。相反，您应该使用时间复杂度为O（N.log（N））低得多的mergesort。

这是一个示例（自上而下的合并排序）：

/* return the comparison status: 0 for equal, <0 if a < b, >0 if a>b */
int compare_ascii(t_list *a, t_list *b) {
    return ft_strcmp(((t_dir *)a->content)->pathname, ((t_dir *)b->content)->pathname);
}

t_list *merge(t_list *a, t_list *b, int (*cmp)(t_list *a, t_list *b)) {
    t_list *head = NULL;  /* head of the merged list */
    t_list **r = &head;   /* pointer to the node link */
    if (a && b) {
        for (;;) {
            if ((*cmp)(a, b) <= 0) {
                /* link the head node of list a */
                *r = a;
                r = &a->next;
                a = a->next;
                if (!a)
                    break;
            } else {
                /* link the head node of list b */
                *r = b;
                r = &b->next;
                b = b->next;
                if (!b)
                    break;
            }
        }
    }
    /* link the remaining part of a or b if any */
    *r = (a == NULL) ? b : a;
    return head;
}

t_list *mergesort(t_list *p, int (*cmp)(t_list *a, t_list *b)) {
    t_list *a, *b, *last = NULL;
    /* find the middle with 2 finger method: a moves twice as fast as b */
    for (a = b = p; a && a->next; a = a->next->next, b = b->next)
         last = b;
    if (last == NULL) {
        /* empty list or single element */
        return p;
    }
    /* split in the middle (before b) */
    last->next = NULL;
    /* sort each half and merge the sorted sublists */
    return merge(mergesort(p, cmp), mergesort(b, cmp), cmp);
}

void sort_ascii(t_list **head) {
    *head = mergesort(*head, compare_ascii);
}

正如rcgldr所评论的那样，自下而上的合并排序通常更快，因为它不需要扫描列表来查找中间元素，由于缓存不匹配，这可能会很昂贵。对应的是它可能执行更多比较，但时间复杂度为O（N.log（N）），并且不是递归的。

这是mergesort使用自底向上合并排序的版本：

t_list *mergesort(t_list *head, int (*cmp)(t_list *a, t_list *b)) {
    t_list *array[32]; // sorted sublists: array[i] has 2**i length if not null
    t_list *result = head;
    int i, top = 0;

    // merge nodes into array
    while (result != NULL) {
        t_list *next = result->next;
        result->next = NULL;
        // merge sorted sublists by increasing power of 2 sizes
        for (i = 0; i < top && array[i] != NULL; i++) {
            result = merge(array[i], result, cmp);
            array[i] = NULL;
        }
        // store the merged list, update top, do not go past end of array
        if (i == top) {
            if (top < 32)
                top++;
            else
                i--;
        }
        array[i] = result;
        result = next;
    }
    // merge all sorted sublists into single list
    result = NULL;
    for (i = 0; i < top; i++) {
        result = merge(array[i], result, cmp);
    }
    return result;
}