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

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

	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;

}

void del(int pos)
{
	Node *temp = head;

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

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

	Node *temp1 = temp->link;
	temp->link = temp1->link;
	free(temp1);
	return;

}

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

	return len(temp->link) + 1;
}

bool find(int val, Node *temp)
{
	if (temp == 0)
	{
		return false;
	}
	if (temp->data == val)
	{
		return true;
	}

	if (find(val, temp->link) == true)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void ror(int k, int sz)
{
	Node *ptr = head;
	//	cout << ptr;
	if (k < 0 || ptr == 0)
	{
		return;
	}

	k = k % sz;
	if (k == 0)
	{
		return;
	}
	Node *temp = head;
	int i = 1;
	while (i < (sz - k))
	{
		//	cout << temp->data << " ";
		temp = temp->link;
		i++;
	}

	Node *temp1 = temp->link;
	head = temp1;
	temp->link = 0;
	//	cout << temp->data;

	while (temp1->link != 0)
	{
		//	cout << "hi" << " ";
		temp1 = temp1->link;

	}
	temp1->link = ptr;

	return;
}

void rol(int k, int sz)
{
	Node *ptr = head;
	if (k < 0 || ptr == 0)
	{
		return;
	}

	k = k % sz;

	if (k == 0)
	{
		return;
	}

	Node *temp = head;
	int i = 1;

	while (i < k)
	{
		temp = temp->link;
		i++;
	}

	Node *temp1 = temp->link;
	head = temp1;
	temp->link = 0;

	while (temp1->link != 0)
	{
		temp1 = temp1->link;
	}
	temp1->link = ptr;
	return;
}

void reverse()
{

	Node *prev = 0, *next = head->link, *cur = head;

	while (cur != 0)
	{
		cur->link = prev;
		prev = cur;
		cur = next;

		if (next)
		{
			next = next->link;
		}

	}
	head = prev;

}

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 = 0;

	if (left == 0)
	{
		return right;
	}

	if (right == 0)
	{
		return left;
	}

	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 *temp)
{
	if (temp == 0 || temp->link == 0)
	{
		return temp;
	}

	Node *mid = getmid(temp);
	Node *nextofmid = mid->link;
	mid->link = 0;

	Node *left = mergesort(temp);
	Node *right = mergesort(nextofmid);

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

}

void swap(int a, int b)
{
	Node *temp = head;
	Node *prev = 0;

	while (temp != 0 && prev->data != a)
	{
		prev = temp;
		temp = temp->link;
	}
	Node *px = temp;
	Node *prevx = prev;

	temp = head;
	prev = 0;

	while (temp != 0 && prev->data != b)
	{
		prev = temp;
		temp = temp->link;
	}

	Node *py = temp;
	Node *prevy = prev;

	Node *ptr;

	ptr = py->link;
	py->link = px->link;
	px->link = ptr;

	if (prevx == 0)
	{
		head = py;
		prevy->link = px;
	}

	if (prevy == 0)
	{
		head = px;
		prevx->link = py;
	}

	if (prevx != 0 && prevy != 0)
	{
		prevx->link = py;
		prevy->link = px;
	}
}

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(891, 1);
	ins(223, 2);
	ins(73211, 3);
	ins(4, 4);
	ins(5, 5);
	ins(7, 6);

	//	del(3);

	//	int sz = len(head);

	//	cout << find(3, head);
	//	int k = 1; //unit to shift

	//	ror(k, sz);

	//	rol(1, sz);

	//	reverse();

	//	getmid(head);

	mergesort(head);

	display();

}