public class MergeLL extends SortBase
{
    /** The head of the linked list */
    Node head = null; 

    /** The Node class for a doubly linked list */
    private class Node { 
        /** The data held in the node */
        final int payload; 
        /** the next node in the list */
        Node next; 
        /** The previous node in the list */
        Node prev;
  
        public Node(int val) 
        { 
            payload = val;
            next=null;
            prev=null; 
        } 
    } 


    /**
     * Sort the linked list using merge sort
     * @param headNode the node at the head of the linked list to be sorted
     * Note that the provided implementation DOES NOT sort
     * @return the node at the head of the sorted linked list.
     */
    public Node mergeSort(Node headNode) {
        return headNode;
    }

    /**
     * Add an integer to the linked list
     * @param new_data the integer to be added
     */
    void push(int new_data) 
    { 
        /* allocate node */
        Node new_node = new Node(new_data); 
  
        /* link the old list off the new node */
        new_node.next = head; 
  
        /* move the head to point to the new node */
        head = new_node; 
    } 
  
    /**
     * Utility function to print the linked list. This function actually prints the list twice
     * Once forward and once backward.
     * @param pfx something to print before actually priting the list
     * @param headref the head of the linked list to be printed
     **/
    void printList(String pfx, Node headref) 
    { 
        System.out.println(pfx);
        if (headref==null)
            return;
        while (true) { 
            System.out.print(headref.payload + " "); 
            if (headref.next==null)
                break;
            headref = headref.next; 
        } 
        System.out.println();
        while (true) {
            System.out.print(headref.payload + " "); 
            if (headref.prev==null)
                break;
            headref = headref.prev; 
        }
        System.out.println();
    } 

  
    public static void main(String[] args) 
    { 
        MergeLL li = new MergeLL(); 
        //For development you may (and should) change the next two lines.
        //In the version you hand in,  the next two lines should be here
        // unless your program cannot sort 4000000 items. In that case, change 
        // 4000000 to the largest number of items your program can sort.
        li.dotest(1, 30, true);
        li.dotest(7, 4000000, false);
    }
    
    /**
     * Run a test
     * @param reps the number of repetitions to run
     * @param siz the number of items to be sorted
     * @param print if true, print lists before and after sorting
     */
    public void dotest(int reps, int siz, boolean print)
    {

        long totaltime = 0;
        for (int r=0; r<reps; r++) {
            head=null;
            int[] aa = fyShuffle(siz);
            for (int aaa : aa)
                push(aaa);

            if (print)
            {
                printList("UNSorted Linked List is:", head); 
            }  
        
            // Apply merge Sort 
	        long stime = System.nanoTime();
            head = mergeSort(head); 
            long etime = System.nanoTime();
            totaltime+=(etime-stime);
    	    if (print)
	        {
	            System.out.println("    Time " + " "  + (etime-stime)/100000);
	            printList("Sorted Linked List is:", head); 
            }
        }
        System.out.println("Average Time " + " "  + totaltime/(reps*100000));

    } 

    /** required to extend SortBase but not used here */
    public void sortInPlace(int[] array) {
    }
}