#include <iostream>
#include <string>
#include <ctime>

using namespace std;

struct node
{
	double key;
	node* next;

	node(double _key, node* _next) : key(_key), next(_next) {}
};

struct nodeQ // for MergeSort
{
	node* head;
	node* tail;
	nodeQ* next;

	nodeQ(node* _head, node* _tail, nodeQ* _next) : head(_head), tail(_tail), next(_next) {}
};

void AddToFront(node*& head, node*& tail, double x)
{
	head = new node(x, head);
	if (!head->next)
		tail = head;
}

void Print(node* head, string info = "", string separator = " ", string prefix = "[", string postfix = "]\n")
{
	cout << info << prefix;
	string sep = "";
	while (head)
	{
		cout << sep << head->key;
		sep = separator;
		head = head->next;
	}
	cout << postfix;
}

void PrintLists(nodeQ* qhead, string info = "")
{
	cout << info;
	if (!qhead)
		return;
	nodeQ* tmp = qhead;
	do
	{
		Print(tmp->head);
		tmp = tmp->next;
	} while (tmp != qhead);
}

void RemoveList(node*& head)
{
	node* tmp;
	while (tmp = head)
	{
		head = head->next;
		delete(tmp);
	}
}

void ShiftToEnd(node*& head1, node*& head, node*& tail)
{
	if (!head1)
		return;

	node* tmp = head1;
	head1 = head1->next;
	tmp->next = nullptr;

	if (!head)
	{
		head = tail = tmp;
		return;
	}
	tail->next = tmp;
	tail = tmp;
}


void SplitList(nodeQ*& qhead, node*& head) // for MergeSort
{
	while (head)
	{
		node* tmphead = nullptr;
		node* tmptail = nullptr;

		double lastkey;
		do
		{
			lastkey = head->key;
			ShiftToEnd(head, tmphead, tmptail);
		} while (head && lastkey <= head->key);

		nodeQ* tmp = new nodeQ(tmphead, tmptail, nullptr);
		if (qhead)
		{
			tmp->next = qhead->next;
			qhead->next = tmp;
		}
		else
			qhead = tmp->next = tmp;

		cout << endl;
		Print(head, "Not splitted part:\n");
		PrintLists(qhead, "Splitted parts:\n");
	}
}

void Merge(node* head1, node* tail1, node* head2, node* tail2, node*& head, node*& tail) // for MergeSort
{
	while (head1&&head2)
		if (head1->key < head2->key)
			ShiftToEnd(head1, head, tail);
		else
			ShiftToEnd(head2, head, tail);
	if (head1)
	{
		tail->next = head1;
		tail = tail1;
	}
	else if (head2)
	{
		tail->next = head2;
		tail = tail2;
	}
}

void SelectionSort(node*& head)
{
	node* headS = NULL;

	while (head)
	{
		node** pMax = &head;
		node** tmp = &(head->next);

		while (*tmp)
		{
			if ((*tmp)->key >= (*pMax)->key)
				pMax = tmp;
			tmp = &((*tmp)->next);
		}

		node* max = *pMax;
		*pMax = (*pMax)->next;

		max->next = headS;
		headS = max;
	}

	head = headS;
}

void InsertionSort(node*& head)
{
	node* headS = NULL;

	while (head)
	{
		node* front = head;
		head = head->next;

		node** tmp = &headS;
		while (*tmp && (*tmp)->key < front->key)
			tmp = &((*tmp)->next);

		front->next = *tmp;
		*tmp = front;
	}

	head = headS;
}

void MergeSort(node*& head, node*& tail)
{
	if (!head)
		return;

	cout << "\n------------------------ SPLITTING ------------------------\n";
	nodeQ* qhead = nullptr;
	SplitList(qhead, head);

	cout << "\n------------------------ MERGING ------------------------\n";
	while (qhead->next != qhead)
	{
		node* tmphead = nullptr;
		node* tmptail = nullptr;
		Merge(qhead->head, qhead->tail, qhead->next->head, qhead->next->tail, tmphead, tmptail);

		nodeQ* tmp = qhead->next;
		qhead->next = tmp->next;
		delete tmp;

		qhead->head = tmphead;
		qhead->tail = tmptail;
		qhead = qhead->next;

		cout << endl;
		PrintLists(qhead, "Splitted parts:\n");
	}

	head = qhead->head;
	tail = qhead->tail;
	delete qhead;
}

int main(void)
{
	node* head = nullptr;
	node* tail = nullptr;

	srand((unsigned)time(nullptr));

	int N = 20;
	for (int i = 0; i < N; i++)
		AddToFront(head, tail, rand() % 20);
	Print(head, "Before sort:\n");

	//SelectionSort(head);
	//InsertionSort(head);
	MergeSort(head, tail);

	Print(head, "\nAfter  sort:\n");

	RemoveList(head);

	return 0;
}