Merge sort circular linked list C

Question

I am trying to merge sort a list in C. I saw code here on French Wikipedia but it gives me an incorrect list (i.e not sorted). The function compiles perfectly though. Please note that I do not really use top, I might take it off the structure soon. Can you help me figuring out what is wrong with this code? I had to translate it from algorithm pseudo-code into C code. Thank you.

P is the unsorted input list. n is the length of the list.

typedef struct s_stack t_stack;

struct s_stack {
    int     nbr;
    int     top;
    struct s_stack  *previous;
    struct s_stack  *next;
};

typedef t_stack *Pile;

t_stack *merge_sort(Pile p, int n) {
    Pile    q;
    int     Q;
    int     P;

    q = NULL;
    Q = n / 2;
    P = n - Q;

    if (P >= 2) {
        q = merge_sort(p, P);
        if (Q >= 2)
            p = merge_sort(q, Q);
    } else {
        q = p->next;
    }
    q = fusion(p, P, q, Q);
    return (q);
}

t_stack *fusion(Pile p, int P, Pile q, int Q) {
    t_stack *tmp;

    tmp = NULL;
    while (1) {
        if (p->next->nbr > q->next->nbr) {
            /* my input list (not sorted) is circular and 
            I checked it is well linked ! This is the reason 
            why I need to do all that stuff with the nodes 
            It is basically supposed to move the node q->next
            after node p */

            tmp = q->next;
            q->next = tmp->next;
            q->next->previous = q;
            tmp->previous = p;
            tmp->next = p->next;
            p->next->previous = tmp;
            p->next = tmp;

            if (Q == 1)
                break;
            Q = Q - 1;
        } else {
            if (P == 1) {
                while (Q >= 1) {
                    q = q->next;
                    Q = Q - 1;
                }
                break;
            }
            P = P - 1;
        }
        p = p->next;
    }
    return (q);
}

Answer 1

Your approach is a bit complicated, but the problem is not so simple, yet you missed some of the necessary steps:

• merge_sort should split the list in 2 halves and recurse unless the list is trivial.
• fusion must use 3 phases: merging the lists by taking the smallest element from each list, then appending the remainder of the first list and finally appending remaining elements form the second list.
• It is generally a bad idea to hide pointers behind typedefs, it makes the code less readable.

Here is a corrected version with a main function for testing with command line arguments.

#include <stdio.h>
#include <stdlib.h>

typedef struct s_stack t_stack;

struct s_stack {
    int     nbr;
    int     top;
    struct s_stack  *previous;
    struct s_stack  *next;
};

t_stack *fusion(t_stack *p, int P, t_stack *q, int Q) {
    t_stack *s;
    t_stack *e;

    s = NULL;
    while (P > 0 && Q > 0) {
        if (p->nbr <= q->nbr) {
            /* select element from p list */
            e = p;
            p = p->next;
            P--;
        } else {
            /* select element from q list */
            e = q;
            q = q->next;
            Q--;
        }
        /* detach e */
        e->previous->next = e->next;
        e->next->previous = e->previous;
        e->next = e->previous = e;
        if (s == NULL) {
            s = e;
        } else {
            /* insert e after s */
            e->previous = s->previous;
            e->next = s;
            s->previous->next = e;
            s->previous = e;
        }
    }
    if (P > 0) {
        /* insert p at the end of s */
        if (s == NULL) {
            s = p;
        }  else {
            /* insert p after s */
            e = p->previous; /* end element of p */
            p->previous = s->previous;
            e->next = s;
            s->previous->next = p;
            s->previous = e;
        }
    }
    if (Q > 0) {
        /* insert q at the end of s */
        if (s == NULL) {
            s = q;
        }  else {
            /* insert q after s */
            e = q->previous; /* end element of p */
            q->previous = s->previous;
            e->next = s;
            s->previous->next = q;
            s->previous = e;
        }
    }
    return s;
}

t_stack *merge_sort(t_stack *s, int S) {
    t_stack *p;
    t_stack *q;
    int     P;
    int     Q;

    if (S < 2) {
        /* single or no elements, already sorted */
        return s;
    }

    /* split p in 2 halves: p[0..P] and q[0..Q] */
    for (q = p = s, P = 0, Q = S; P < Q; P++, Q--) {
        q = q->next;
    }

    p = merge_sort(p, P);
    q = merge_sort(q, Q);
    s = fusion(p, P, q, Q);
    return s;
}

t_stack *append(t_stack *s, int value) {
    t_stack *e = malloc(sizeof(*e));
    e->top = 0;
    e->nbr = value;
    e->next = e->previous = e;
    if (s == NULL) {
        s = e;
    } else {
        /* insert e after s */
        e->previous = s->previous;
        e->next = s;
        s->previous->next = e;
        s->previous = e;
    }
    return s;
}

void print_stack(const char *legend, t_stack *s, int S) {
    printf("%s:", legend);
    while (S-- > 0) {
        printf(" %d", s->nbr);
        s = s->next;
    }
    printf("\n");
    fflush(stdout);
}

int main(int argc, char *argv[]) {
    t_stack *s = NULL;
    int S = 0;
    int i;

    for (i = 1; i < argc; i++) {
        s = append(s, atoi(argv[i]));
        S++;
    }
    print_stack("original stack", s, S);
    s = merge_sort(s, S);
    print_stack("sorted stack", s, S);
    return 0;
}