#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
void inserathead(node *&head, int d)
{
if (head == NULL)
{
head = new node(d);
return;
}
node *temp = new node(d);
temp->next = head;
head = temp;
}
void print(node *head)
{
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << “\n”;
}
void insertanywhere(node *&head, int d, int p)
{
int x = 0;
if (p == 0)
{
if (head == NULL)
{
head = new node(d);
return;
}
node *temp = new node(d);
temp->next = head;
head = temp;
}
else
{
p--;
node *temp = head;
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;
}
}
void deletehead(node *&head)
{
if (head == NULL)
{
return;
}
node *temp = head;
temp = temp->next;
delete head;
head = temp;
}
void deleteinmiddle(node *&head, int p)
{
if (p == 0)
{
deletehead(head);
return;
}
if (head == NULL)
{
return;
}
node *temp = head;
node *prev = temp;
int i = 0;
while (i != p)
{
prev = temp;
temp = temp->next;
i++;
}
prev->next = temp->next;
delete temp;
}
int search(node *&head, int key)
{
node *temp = head;
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;
node *head = NULL;
while (cin >> d)
{
if (d == -1)
{
return head;
}
inserathead(head, d);
}
return head;
}
// cascading of operators
ostream &operator<<(ostream &os, node *head)
{
if (head == NULL)
{
os << “Empty list\n”;
return os;
}
print(head);
return os;
}
istream &operator>>(istream &is, node *&head)
{
head = take_input();
return is;
}
void reverse(node *&head)
{
node *c = head;
node *p = NULL;
node *n;
while (c != NULL)
{
n = c->next;
c->next = p;
p = c;
c = n;
}
head = p;
}
node *recReverse(node *&head)
{
if (head->next == NULL || head == NULL)
{
return head;
}
// rec case
node *shead = recReverse(head->next);
node *temp = shead;
while (temp->next != NULL)
{
temp = temp->next;
}
head->next = NULL;
temp->next = head;
return shead;
}
node *midpoint(node *head)
{
if (head->next == NULL || head == NULL)
{
return head;
}
node *slow = head;
node *fast = head->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;
}
node *mergesort(node *head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
node *mid = midpoint(head);
node *a = head;
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();
}