merge sort implementation with linked list

  c++, linked-list, mergesort

I am trying to implement merge sort in a linked list in c++. When I execute my code, it runs infinitely no. of time. When I debug it, I found that my mergesort function runs only for the left half infinite number no. of times.I mean it never comes out from left half. That function never called for the right half. I am pasting my whole code link here. Can anyone tell me why the function runs infinitely and what modifications I have to make to my code?

 #include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007

struct Node
{
int data;
struct Node *link;
};
Node *head = NULL;
void ins(int data, int pos)
{
Node *ptr = new Node();
ptr->data = data;
ptr->link = NULL;

if (pos == 1)
{
    ptr->link = head;
    head = ptr;
    return;
}

Node *temp = new Node();
temp = head;
for (int i = 1; i < pos - 1; i++)
{
    temp = temp->link;
}

ptr->link = temp->link;
temp->link = ptr;
return;

}


Node* getmid(Node *temp)
{
if (temp == 0)
{
    return temp;
}

Node *a = temp;
Node *b = temp;

while (b->link != 0)
{
    b = b->link;
    a = a->link;
    if (b->link != 0)
    {
        b = b->link;
    }
    else
    {
        break;
    }
}

return a;
}

Node* merge(Node *left, Node *right)
{
Node *res = NULL;

if (left == NULL || right == NULL)
{
    if (left == NULL)
    {
        return right;
    }
    if (right == NULL)
    {
        return left;
    }
    else
    {
        return NULL;
    }
}

else if ((left->data) < (right->data))
{
    res = left;
    res->link = merge(left->link, right);
}
else
{
    res = right;
    res->link = merge(left, right->link);
}

return res;
}

Node* mergesort(Node *head)
{
if (head == NULL || (head->link) == NULL)
{
    return head;
}

Node *mid = getmid(head);
Node *left = head;
Node *right = mid->link;
mid->link = NULL;

left = mergesort(left);
right = mergesort(right);

Node *c = merge(left, right);
return c;

}


void display()
{
Node *t = head;

while (t != 0)
{
    cout << t->data << " ";
    t = t->link;
}
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

ins(8, 1);
ins(23, 2);
ins(73, 3);
ins(4, 4);
ins(5, 5);
ins(7, 6);

mergesort(head);

display();

}

In the above code, ins function is used to insert the node. getmid function is used for getting the address of the middle node. merge function is used to sort the left and right half. And mergesort function is used to divide the list into 2 half and call each half.display function is used for print linked list

Source: Windows Questions C++

LEAVE A COMMENT