Linked List Merge Sort

This is a discussion on Linked List Merge Sort within the C++ Programming forums, part of the General Programming Boards category; As I am a fairly new c++ programmer I was given this mergesort, for a linked list. I do not ...

  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
    RoD
    RoD is offline
    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, 11:03 AM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21