import java.lang.Object.* ;

class  MergeSort
{
	public int realValue;
	Node root;
	public LinkedList l2 = new LinkedList();
	public LinkedList L1= new LinkedList();
	
	LinkedList mergeSort(LinkedList LL)
	{
		LL=mergeSortAux(LL);
		return LL;		//return the linkedlist;
	}
	
	LinkedList mergeSortAux(LinkedList LL)
	{
		int value = LL.mySize();
		
		if(value<2) //if there's only one node in the list
		{
			return LL;
		}
		
		realValue = abs(value/2);

		l2=splitList(LL); //split the list and updated 
									//the second list.
		
		L1 = mergeSortAux(L1);

		l2 = mergeSortAux(l2);
		
				
		return mergeLists(L1,l2);		//return the linkedlist;
	}
	
	LinkedList splitList(LinkedList listToSplit)
	{
		LinkedList L = new LinkedList();
		
		int count = 1;

		while(count!=realValue)
		{
			root=listToSplit.anchor; //set root to be equal to anchor
			if(root.next=null&&count==1)//if there's only one node in the list
			{
				return null;
			}
			root=root.next;
			count++;
		}
		
		L.anchor=root.next;	//set the 2nd halves of the list to L
		
		root.next=null;	// set the end of the 1st halves of the list 
		
		listToSplit.anchor=root;	// update the root of the first list
		
		L1 = listToSplit; //update the first list after the list is 
							//divided.

		return L; //return the second linkedlist;

	}

	LinkedList mergeLists(LinkedList list1, LinkedList 1ist2)
	{
		LinkedList L3 = new LinkedList();

		while(true)
		{
			if(list1.isEmpty()&&list2.isEmpty())
			{
				return null;
			}
			else		//while the lists are not empty
			{
				if(list1.senseHead()<list2.senseHead())
				{
					L3.insertToTail(list1.removeHead()); 
				}
				else
				{
					L3.insertToTail(list2.removeHead());
				}
			}
			
			return L3;		//return the linkedlist;
		}
	}
}