Merge-sorting a linked list

Question

I'm required to sort a Linked list using merge sort. I've put together this code, but I'm running into a weird error.

My linked list is populated by random numbers. However, after sorting, it only displays numbers that are larger than the first element of the linked list, in sorted order.

Here is some of my code:

node* MergeSort(node *my_node)
{
    node *secondNode;

    if (my_node == NULL)
        return NULL;
    else if (my_node->next == NULL)
        return my_node;
    else
    {
        secondNode = Split(my_node);
        return Merge(MergeSort(my_node),MergeSort(secondNode));
    }
}

node* Merge(node* firstNode, node* secondNode)
{
    if (firstNode == NULL) return secondNode;
    else if (secondNode == NULL) return firstNode;
    else if (firstNode->number <= secondNode->number) //if I reverse the sign to >=, the behavior reverses
    {
        firstNode->next = Merge(firstNode->next, secondNode);
        return firstNode;
    }
    else 
    {
        secondNode->next = Merge(firstNode, secondNode->next);
        return secondNode;
    }
}

node* Split(node* my_node)
{
    node* secondNode;

    if (my_node == NULL) return NULL;
    else if (my_node->next == NULL) return NULL;
    else {
        secondNode = my_node->next;
        my_node->next = secondNode->next;
        secondNode->next = Split(secondNode->next);
        return secondNode;
    }
}

tgmath · Accepted Answer · 2011-04-12 08:12:34Z

2

I have tried your code and it works perfectly.

Have you looked at the right list in the end? Your new head of the list is not the previous head, but the return value of the Merge function.

printList(myList);
node* sortedList =  MergeSort(myList);
printList(sortedList); //whole list sorted
printList(myList); //list (of elements not smaller that first element) sorted

and printList() is the obvious function:

void printList(node* my_node){
    if(my_node == NULL) return;
    else {
        std::cout<<my_node->number<<" "<<std::endl; 
        printList(my_node->next);   
    }
}

answered Apr 12, 2011 at 8:12

tgmath

13.7k2 gold badges18 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ayush Over a year ago

Ah, yes. I see where I was going wrong. Thanks. This fixed it.

Collectives™ on Stack Overflow

Merge-sorting a linked list

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related