Why do I get stack overflow error when I use this function for Merge Sort(using Linked Lists)?

Question

I am using a mid_element() function to return the address of the middle node and a Merge() function to merge two sorted linked lists. Both these functions work fine. But I have attached the code just in case. I went through the merge sort algorithm that partitions the linked list into two, one containing the first node till the middle node and the next from mid+1 to the end. And of course the next pointer of middle node is set to null. Then we call merge sort recursively on both halves and finally merge the two. I did the same but I end up with a stack overflow error. Please help. Middle element function:

Node *mid_element(Node *head)
{
    if(head==NULL || head->next==NULL)
        return head;
    Node *slow=head,*fast=head->next;
    while(fast!=NULL)
    {
        if(fast->next==NULL)
        {
            slow=slow->next;
            break;
        }
        else
        {
            fast=fast->next->next;
            slow=slow->next;
        }
    }
    return slow;
}

Merge function:

Node *Merge(Node *h1,Node *h2)
{
    Node *h=h1->data<h2->data?h1:h2,*t=h;
    h1=h1->next;
    while(h1!=NULL && h2!=NULL)
    {
        if(h1->data<h2->data)
        {
            t->next=h1;
            t=t->next;
            h1=h1->next;
        }
        else
        {
            t->next=h2;
            t=t->next;
            h2=h2->next;
        }
    }
    if(h1!=NULL)
        t->next=h1;
    if(h2!=NULL)
        t->next=h2;
    return h;
}

Merge Sort function:

Node *MergeSort(Node *head)
{
    if(head==NULL || head->next==NULL)
        return head;
    else
    {
        Node *mid=mid_element(head);
        Node *temp=mid->next;
        mid->next=NULL;
        Node *res1=MergeSort(head);
        Node *res2=MergeSort(temp);
        Node *res=Merge(res1,res2);
        return res;
    }
}

Definition of Node:

class Node
{
public:
    int data;
    Node *next;

    Node(int data)
    {
        this->data=data;
        next=NULL;
    }

};

I am using a function to get the input. The user enters space separated list of numbers with -1 indicating end of the list. Input function:

Node *takeInput()
{
    int data;
    Node *head=NULL,*temp=NULL,*curr=NULL;
    do{
        cin >> data;
        if(data!=-1)
        {
            temp=new Node(data);
            if(head==NULL)
            {
                head=curr=temp;
            }
            else
            {
                curr->next=temp;
                curr=curr->next;
            }

        }
    }while (data!=-1);
    return head;
}

Regarding the size of the list, I just checked with lists just 5-6 elements long and it crashed.

How large is the list? And can you please try to create a minimal reproducible example to show us, including how you create the most simple and shortest list to create the crash for you. — Some programmer dude
consider the case when the linked list contains two elements a->b. mid_element returns b. temp in MergeSort becomes b->next i.e. NULL. res2 = MergeSort(NULL) = NULL and res1 = MergeSort(head) and here the linked list sent to MergeSort is again a->b. So, this process goes on indefinitely and the stack eventually runs out. — susanth29
@susanth29 thank you for the explanation. Do I have to handle the size=2 case separately or is there some other way? — Arman Atibudhi
@ArmanAtibudhi Handle the size=2 case separately. This way you can correct your code with fewer changes. Also as mentioned by Tim in answer, be careful about accessing data from a NULL pointer in the Merge function. — susanth29

Tim Randall Tim Randall · Accepted Answer · 2021-08-30T15:58:48

This line in Merge() dereferences a potentially null pointer.

Node *h=h1->data<h2->data?h1:h2,*t=h;

And it is potentially null because mid_element() contains this line

if(head==NULL || head->next==NULL)
    return head;

... which can return a pointer whose next element is null, and MergeSort() takes that return value, gets the next element that might be null, and passes it to Merge().

Bottom line: more null checks needed before dereferencing pointers.

Why do I get stack overflow error when I use this function for Merge Sort(using Linked Lists)?

1 Answers