/* Mergesort on linked lists  // uses LinkedList.java
*/

public class Listsort
{
    // polymorphic function constructs sorted linked list
    public static <T extends Comparable<T>> LinkedList<T> mergesort(LinkedList<T> A)
    {
	// base case: return if list is too small:
	if (A==null || A.size<2) return A;
	// divide linked list in two:
	LinkedList<T> B = A.split();
	// recursively sort each half:
	A = mergesort(A);
	B = mergesort(B);
	// merge two sorted lists 
	LinkedList<T> C = new LinkedList<T>();
	cell<T> i = A.first;
	cell<T> j = B.first;
	while (i!=null && j!=null)
	    {
		if (i.item.compareTo(j.item)<0)
		    { C.add(i.item);  i=i.next; }
		else
		    { C.add(j.item);  j=j.next; }
	    }
	// at this point, need to add remainder to C:
	while (i!=null) { C.add(i.item);  i=i.next; }
	while (j!=null) { C.add(j.item);  j=j.next; }
	return C;
    }//mergesort

    public static <T extends Comparable<T>> LinkedList<T> insertsort(LinkedList<T> A)
    {
	LinkedList<T> B = new LinkedList<T>();
	for(cell<T> i=A.first;i!=null;i=i.next)
	    {
		// insert i.item into B, keeping it sorted
		cell<T> j = B.first;
		if (j==null || i.item.compareTo(B.first.item)<0) 
		    {B.push(i.item); return B;}
		while (j.next!=null && i.item.compareTo(j.next.item)>0) 
		    j=j.next;
		j.next = new cell<T>(i.item,j.next);
		B.size++;
	    }
	return B;
    }// insertionsort  (need access to contents of B class)

    public static void bubblesort(double[] A) // to compare
    {
	for(int i=0;i<A.length-1;i++)
	    for(int j=0;j<A.length-1-i;j++)
		{
		    if (A[i]>A[j])
			{
			    double tmp = A[i];  A[i] = A[j];  A[j]=tmp;
			}
		}
    }// bubblesort

    // check that a list is indeed sorted
    public static <T extends Comparable<T>> boolean sorted(LinkedList<T> A)
    {
	if (A==null || A.size()<2) return true;
	cell<T> current = A.first;
	while (current.next!=null)
	    {
		int r = current.item.compareTo(current.next.item);
		if (r>0) return false;
		current = current.next;
	    }
	return true;
    }

    public static void main(String[] av)
    {
	int n = Integer.parseInt(av[0]); // size of list
	// randomly generate list
	LinkedList<Double> A = new LinkedList<Double>();
	double[] AA = new double[n];
	for(int i=0;i<n;i++)
	    {   
		double x = Math.random()*n;
	        A.add(x);
		AA[i] = x;
	    }
	long t1 = System.currentTimeMillis(); // record time
	LinkedList<Double> B = mergesort(A);
	long t2 = System.currentTimeMillis(); 
	if (!sorted(B)) System.out.println("OOPS!");
	System.out.println("time to mergesort ~= "+(t2-t1)+" ms");
	System.out.flush();
	//	System.out.println(B);  // test on small arrays only

	long t3 = System.currentTimeMillis(); 	
	bubblesort(AA);
	long t4 = System.currentTimeMillis(); 	
	System.out.println("time to bubblesort array ~= "+(t4-t3)+" ms");
    }
}//listsort