Thread: Linked List Merge Sort

As I am a fairly new c++ programmer I was given this mergesort, for a linked list. I do not quite understand it, if someone could comment it it would be much apreciated.

Code:

struct node {
    struct node *next;
    char name[100];
} *list;

static void recurse_merge_sort(struct node **root, int(*cmp)(struct node *, struct node *))
{
    struct node *a, *b;
    for(a = b = *root; (b = b->next) && (b = b->next); a = a->next);
    b = a->next;
    a->next = 0;
    a = *root;
    if(a->next) recurse_merge_sort(&a, cmp);
    if(b->next) recurse_merge_sort(&b, cmp);
    while(a && b) {
        if(cmp(a, b) < 0) {
            *root = a; root = &a->next; a = a->next;
        } else {
            *root = b; root = &b->next; b = b->next;
        }
    }
    *root = a ? a : b;
}
void merge_sort(struct node **root, int(*cmp)(struct node *, struct node *))
{
    if(*root && (*root)->next) recurse_merge_sort(root, cmp);
}
int node_cmp(struct node *a, struct node *b) {
    return(strcmp(a->name, b->name));
}

Rather then comment the entire code block, why not pick out what parts you dont understand? With a little effort you could probably read it yourself making little notes and begin to understand alot of what is going on.

What I really dont understand is basically the function prototype. I dont understand why there are two ** before the root, i dont know what int(*cmp) is for and i dont understand the basic setup of (struct node *, struct node *)). Thanks

Code:

static void recurse_merge_sort(struct node **root, int(*cmp)(struct node *, struct node *))