# Merge sort algorithm

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)

class node
{
public:
int data;
node *next;
node(int d)
{
data = d;
next = NULL;
}
};
// pass by reference
{
{
return;
}
node *temp = new node(d);
}
{
{
cout << head->data << " ";
}
cout << “\n”;
}
void insertanywhere(node *&head, int d, int p)
{
int x = 0;

``````if (p == 0)
{
{
return;
}
node *temp = new node(d);
}
else
{
p--;

for (int i = 0; i < p; i++)
{
node *lim = temp;
temp = temp->next;
if (temp == NULL)
{
temp = lim;
break;
}
}
node *t = new node(d);
t->next = temp->next;
temp->next = t;
}
``````

}
{
{
return;
}
temp = temp->next;
}
{
if (p == 0)
{
return;
}
{
return;
}
node *prev = temp;
int i = 0;
while (i != p)
{

``````    prev = temp;

temp = temp->next;

i++;
}
prev->next = temp->next;
delete temp;
``````

}
{
int i = -1;
int x = -1;
while (temp != NULL)
{
i++;
if (temp->data == key)
{
x = 0;
break;
}
temp = temp->next;
}
if (x == -1)
{
return -1;
}
return i;
}
node *take_input()
{
int d;
while (cin >> d)
{
if (d == -1)
{
}
}
}
{
{
os << “Empty list\n”;
return os;
}

``````print(head);
return os;
``````

}
{
return is;
}
{
node *p = NULL;
node *n;
while (c != NULL)
{

``````    n = c->next;
c->next = p;
p = c;
c = n;
}
``````

}
{
{
}
// rec case
while (temp->next != NULL)
{
temp = temp->next;
}
}
{
{
}
while (fast->next != NULL && fast != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
node *merge(node *a, node *b)
{
if (a == NULL)
{
return b;
}
if (b == NULL)
{
return a;
}
node *c;
if (a->data < b->data)
{
c = a;
c->next = merge(a->next, b);
}
else
{
c = b;
c->next = merge(a, b->next);
}
return c;
}
{

``````if (head == NULL || head->next == NULL)
{

}

node *b = mid->next;
mid->next = NULL;

a = mergesort(a);
b = mergesort(b);
node *c = merge(a, b);
return c;
``````

}
void solve()
{
node *a = NULL;
cin >> a;
cout << “sorted\n”;
a = mergesort(a);
cout << a;
}

signed main()
{
int t;
t=1
while (t–)
solve();
}

Kindly provide code in link format