CODEWITHSUNDEEP
c++mergesortsingly-linked-list
Reginald
Reginald

Reputation: 23

C++ Merge sort of linked list is not sorting the first two indices

I am getting a bit lost trying to figure out how to recursively merge sort my linked list. I have tried following some guides but I'm getting a bit lost with all the pointers and recursion. It feels like the problem is with the merge function once the lists have a single node each.

I have a Node class and a list class. I have left out other member functions to make it more readable. Here are the classes. Sorry some of the variable names aren't the best in the functions.

class Node {
  public:
    int val;
    Node *next;
};

class Linked_list {
  private:
    unsigned int length;
    Node *head;
    Node *tail;
  public:
    void sort_ascending();
    void merge_sort(Node **);
    void halve(Node *&, Node *&, Node *&);
    Node* merge(Node *, Node *);
};

I start with sort_ascending() which creates a Node pointer and sets it to the first node in the list and then calls merge_sort with the pointer as a parameter. 

void Linked_list::sort_ascending() {
    Node *h = head->next;
    merge_sort(&h);
}

merge_sort checks if the first two indices are NULL, returns if they are. Otherwise the linked list is halved.

void Linked_list::merge_sort(Node **h) {
    Node *t = *h;
    Node *a;
    Node *b;
    if ((t == NULL) || (t->next == NULL)) {
        return;
    }
    halve(t, a, b);
    merge_sort(&a);
    merge_sort(&b);
    *h = merge(a, b);
    return;
}

Here is the function for splitting the list in halves. 

void Linked_list::halve(Node *&t, Node *&a, Node *&b) {
    Node *h1 = t;
    Node *h2 = t->next;
    while (h2 != NULL) {
        h2 = h2->next;
        if (h2 != NULL) {
            h1 = h1->next;
            h2 = h2->next;
        }
    }
    a = t;
    b = h1->next;
    h1->next = NULL;
}

Finally the merge function.

Node *Linked_list::merge(Node *a, Node *b) {
    Node *h = NULL;
    if (a == NULL) {
        return b;
    }
    if (b == NULL) {
        return a;
    }
    if (a->val <= b->val) {
        h = a;
        h->next = merge(a->next, b);
    } else {
        h = b;
        h->next = merge(a, b->next);
    }
    return h;
}

When I run my program and enter/print a few values I get:

9 4 32 2 6

Then when I sort it the output becomes: 

9 4 2 6 32

Upvotes: 2

Views: 150

Answers (2)

Jinu
Jinu

Reputation: 586

Other reason than the one @VeryBhatti pointed out,

while(h2 != NULL){
    h2 = h2->next;
    if(h2 != NULL){
        h1 = h1->next;
        h2 = h2->next;
    }
}

I don't get the logic of your halve function. As the h1 is also moving along h2, when the while statement breaks, the h1 will always point at second to the last element instead of the center.

Why not use length variable to halve the list? Simplifying your code will significantly help you debug the code yourself.

Also, using both reference and pointer at the same time seems to be complicating your code. What I would recommend is to first try implementing it in c style instead of cpp style. Because you are using a linked list, you should be able to implement this without using pointer to a pointer.

Again, try to simplify your code as possible and look for other merge sort samples too.

Upvotes: 2

VeryBhatti
VeryBhatti

Reputation: 129

In the sortAscending function

void Linked_list::sort_ascending(){
   Node *h = head->next;
   merge_sort(&h);
}

See above that you are pointing node*h to next of head. Not head itself. And maybe thats why it excludes the first item i.e head itself while sorting the linked list.

Upvotes: 2

Related Questions