Thread: Linked List Merge Sort

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    23

    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));
    }

  2. #2
    Redundantly Redundant RoD's Avatar
    Join Date
    Sep 2002
    Location
    Missouri
    Posts
    6,331
    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.

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    23
    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 *))

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM