#include <stdio.h>
#include <windows.h> //for rand();
#include <conio.h> // for getch();

class PrecisionTime
{
private:
	LARGE_INTEGER freq, ts;

public:
	PrecisionTime() { QueryPerformanceFrequency(&freq);	}

	//returns the current tick count in seconds
	double GetTime()
	{
		QueryPerformanceCounter(&ts);
		return (double)ts.QuadPart/(double)freq.QuadPart;
	}
};

class cNode
{
public:
	cNode * next;
	int x;

	cNode()
	{
		x = 0;
		next = 0;
	}

	cNode(cNode &node)
	{
		x=node.x;
		next = 0;
	}

	cNode(cNode * node)
	{
		x=node->x;
		next = 0;
	}

};

class cNodeHandler
{
public:
	cNode * head;
	cNode * tail;
	int count;

	cNodeHandler()
	{
		head = 0;
		tail = 0;
		count = 0;
	}

	~cNodeHandler()
	{
		if(head!=0)
		{
			cNode * current=head;
			while(current!=0)
			{
				current=current->next;
				delete head;
				head = current;
			}
			head = 0;
			tail = 0;
		}
	}

	void addNode(cNode &node)
	{
		if(head==0)
		{
			head = new cNode(node);
			tail = head;
		}
		else
		{
			tail->next = new cNode(node);
			tail=tail->next;
		}
		count++;
	}

	void toString()
	{
		cNode * current = head;
		while(current!=0)
		{
			printf("%i:\t%i\n",current,current->x);
			current=current->next;
		}
	}

	void Sort()
	{
		head = MergeSort_Rec(head, count);
		cNode * current = head;
		while(current->next!=0)
			current=current->next;
		tail = current;
	}

	cNode * MergeSort_Rec(cNode * top, int size)
	{
		cNode * first = 0;
		cNode * second = 0;
		cNode * hf = 0;
		cNode * hs = 0;

		int j;

         if (size <= 1) 
			 return top;
         
		 //make a sublist "first" with one half of the nodes
		if(top!=0)
		{
			first = new cNode(top);
			hf = first;
			top = top->next;
			for(j=1;j<size/2 && top!=0;j++)
			{
				first->next = new cNode(top);
				first=first->next;
				top=top->next;
			}
			first = MergeSort_Rec(hf,(size/2));
	    }

         //make a sublist "second" with the rest of the nodes
		if(top != 0)
		{
			 second=new cNode(top);
			 hs=second;
			 top=top->next;
			 for(j=1;j<(size+1)/2 && top!=0; j++)
			 {
				 second->next = new cNode(top);
				 second = second->next;
				 top=top->next;
			 }
	        second = MergeSort_Rec(hs,(size+1)/2);
		 }
        return MergeNodes(first,second);
	}

	cNode * MergeNodes(cNode * first, cNode * second)
	{
		cNode * combined = 0;
		cNode * top = 0;
		cNode * temp = 0;

		if (first == 0) 
			return second;
		if (second == 0) 
			return first;

		//Make a list "combined".  move the one node with the larger of
		//the two values at the beginning of "first" or "second" into the new
		//list.  Note, the node chosen here should no longer be in either
		//first or second.
		if(first->x<second->x)
		{
			combined = new cNode(first);
			temp = first;
			first = first->next;
			delete temp;
		}
		else
		{
			combined = new cNode(second);
			temp = second;
			second = second->next;
			delete temp;
		}

		top=combined;
		while (first !=0 && second != 0)
		{
			//append the node with the larger of the two values at the
			//beginning "first" and "second" to combined.  Note, the
			// node chosen here should no longer be in either first or second
			if(first->x<second->x)
			{
				combined->next = new cNode(first);
				combined = combined->next;
				temp = first;
				first = first->next;
				delete temp;
			}
			else
			{
				combined->next = new cNode(second);
				combined = combined->next;
				temp = second;
				second = second->next;
				delete temp;
			}
		}
		while(first != 0)
		{
			//append the rest of first to combined
			combined->next = new cNode(first);
			combined = combined->next;

			temp = first;
			first = first->next;
			delete temp;
		}
		while(second !=0)
		{
			//append the rest of second to combined
			combined->next = new cNode(second);
			combined = combined->next;
			temp = second;
			second = second->next;
			delete temp;
		}
		return top;
	}
};

void main()
{
	PrecisionTime pTime;

	cNodeHandler nodes;
	cNode temp;
	for(int j=0;j<10000;j++)
	{
		temp.x=rand()%1000;
		nodes.addNode(temp);
	}
	double a = pTime.GetTime();
	nodes.Sort();
	printf("time: %f\n",pTime.GetTime()-a);
   getch();
}