сложность сортировки слиянием со связанным списком

В вашем коде есть опечатка. После исправления он действительно стабилен и имеет O(n log n) сложность. Хотя, конечно, вам действительно следует переопределить свой merge как цикл вместо рекурсии. В C нет оптимизации хвостовых вызовов (верно?), Так что это может все испортить:

struct node *mergesort(struct node *head){

    struct node *head_one;
    struct node *head_two;
    if((head==NULL) ||(head->next==NULL))
         return head;
    head_one=head;
    head_two=head->next;
    while( (head_two!=NULL) &&(head_two->next!=NULL)){
        head=head->next;
        // head_two=head->next->next;      // -- the typo, corrected:
        head_two=head_two->next->next;
        }
    head_two=head->next;
    head->next=NULL;
    return merge(mergesort(head_one),mergesort(head_two));
    }

И пока мы занимаемся этим, измените рабочий процесс с

    return merge(mergesort(head_one),mergesort(head_two));

to

    struct node *p1, *p2; 
    // ......
    p1 = mergesort(head_one);
    p2 = mergesort(head_two);
    return merge(p1,p2);

таким образом будет намного проще работать со стеком (будет использоваться гораздо меньше его).

В общем, это так называемая сортировка слиянием сверху вниз. Вы также можете сделать это снизу вверх, сначала отсортировав последовательные фрагменты по два элемента в каждом, затем объединив их в (таким образом, теперь отсортированные) фрагменты из 4 элементов, а затем объединив эти попарно, на куски по 8 элементов и т. д., пока не останется только один кусок - отсортированный список.

Чтобы получить дополнительную привлекательность (и эффективность), вместо того, чтобы начинать с двух частей, начните с разделения списка на монотонные прогоны, то есть увеличивающие последовательности и убывающие последовательности - повторно связывая последние в обратном порядке. по мере продвижения - таким образом, исходный список сегментируется в соответствии с его внутренним порядком, поэтому, вероятно, будет меньше начальных фрагментов для слияния; затем продолжайте объединять эти попарно несколько раз, как и раньше, пока в конце не останется только один.

Как не реализовывать сортировку слиянием для связанных списков

• не делите список рекурсивно пополам - произвольный доступ не бесплатен
• не делить на подсписки размером 1 и n - 1, как объяснил ruakh

Как реализовать сортировку слиянием для связанных списков

Вместо использования деления пополам создайте списки, поддерживая стек уже отсортированных подсписок. То есть начните с помещения списков размера 1 в стек и сливайте его вниз, пока не дойдете до списка большего размера; на самом деле вам не нужно хранить размеры списков, если вы можете понять математику, стоящую за этим.

Алгоритм сортировки будет стабильным, если есть функция слияния. Стабильная версия построит объединенный список с нуля, всегда беря один элемент из списков и используя первый список в случае равенства. Нестабильная, но более эффективная версия будет добавляться в объединенный список по частям, избегая ненужного повторного связывания после каждого элемента.

Сортировка слиянием означает разделение и слияние. Разделение в приведенном ниже фрагменте не идеально (оно приводит к квадратичному поведению при одинаково распределенных длинах прогонов, см. Комментарий Кристофа)), но оно поможет:

#include <stdio.h>
#include <string.h>

struct llist {
        struct llist *next;
        char *payload;
        };

int llist_cmp(struct llist *l, struct llist *r);
struct llist * llist_split(struct llist **hnd
                        , int (*cmp)(struct llist *l, struct llist *r) );
struct llist * llist_merge(struct llist *one, struct llist *two
                        , int (*cmp)(struct llist *l, struct llist *r) );
struct llist * llist_sort(struct llist *ptr
                        , int (*cmp)(struct llist *l, struct llist *r) );

struct llist * llist_split(struct llist **hnd, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *this, *save, **tail;

for (save=NULL, tail = &save; this = *hnd; ) {
        if (! this->next) break;
        if ( cmp( this, this->next) <= 0) { hnd = &this->next; continue; }
        *tail = this->next;
        this->next = this->next->next;
        tail = &(*tail)->next;
        *tail = NULL;
        }
return save;
}

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = one; one=one->next; }
        else { *tail = two; two=two->next; }
        }
*tail = one ? one: two;
return result;
}
struct llist * llist_sort(struct llist *ptr, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *save;

save=llist_split(&ptr, cmp);
if (!save) return ptr;

save = llist_sort(save, cmp);

return llist_merge(ptr, save, cmp);
}

int llist_cmp(struct llist *l, struct llist *r)

{
if (!l) return 1;
if (!r) return -1;
return strcmp(l->payload,r->payload);
}


struct llist lists[] =
{{ lists+1, "one" }
,{ lists+2, "two" }
,{ lists+3, "three" }
,{ lists+4, "four" }
,{ lists+5, "five" }
,{ lists+6, "six" }
,{ lists+7, "seven" }
,{ lists+8, "eight" }
,{ lists+9, "nine" }
,{ NULL, "ten" }
        };

int main()
{
struct llist *root,*tmp;

root = lists;

fprintf(stdout, "## %s\n", "initial:" );
for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%s\n", tmp->payload);
        }

fprintf(stdout, "## %s\n", "sorting..." );
root = llist_sort(root, llist_cmp);
for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%s\n", tmp->payload);
        }
fprintf(stdout, "## %s\n", "done." );

return 0;
}