// MergeSort.java
// Merge Sort Parallel Test...
// Bryan Chadwick : Sep. 2008


// All the needed functionality to run simple parallel tests on
//   multiple processors.
// Real (pretty good) results with as little as 20,000 elements:
//   java -Xss2M MergeSort 20000 
// Where -Xss2M tells Java to use 2Mb thread stacks (functional lists
//   are tough without proper tail recursion...)
public class MergeSort{
    static void p(String s){ System.out.println(s); }

    // Main Method
    public static void main(String[] s){
        int len = s.length>0?Integer.parseInt(s[0]):2000;
    
        L<Integer> l = rand(new id(), len);
        p(" Length = "+len);

        // Sequential, Parallel, and Array based Sorts...
        p("  Sort: "+new Sorter<Integer>().timesort(l));
        p(" PSort: "+new PSorter<Integer>().timesort(l));
        p(" ASort: "+new ASorter<Integer>().timesort(l, new Integer[len]));
    }

    // Create a D from an integer... so we can build random lists
    //   of different kinds of things for testing
    static abstract class Creator<D>{ abstract D make(int i); }

    // ID for Integers
    static class id extends Creator<Integer>{
        Integer make(int i){ return i; }
    }
    
    //  Make a List with a Creator and integer parameters
    static <D extends Comparable<D>> L<D> make(D ... xs){ return make(xs,0,xs.length); }
    static <D extends Comparable<D>> L<D> make(D[] xs, int i, int len){
        return (i==len)?new L<D>():make(xs,i+1,len).push(xs[i]);
    }
    // Make a List with a Creator and integer parameters
    static <D extends Comparable<D>> L<D> make(Creator<D> c, int ... xs){
        return make(c,xs,xs.length-1);
    }
    // Same here... but from an array, where 'i' is the index currently
    //   being worked on (count down)
    static <D extends Comparable<D>> L<D> make(Creator<D> c, int[] xs, int i){
        return (i < 0)?new L<D>():make(c,xs,i-1).push(c.make(xs[i]));
    }

    // Return a Random integer in [0..19]
    static int randInt(){ return (int)(Math.random()*20); }
    // Make a List with a Creator and random integers
    static <D extends Comparable<D>> L<D> rand(Creator<D> c, int k){
        return (k==0?new L<D>():rand(c,k-1).push(c.make(randInt())));
    }
    
    // Dynamic Sorter Object
    static class Sorter<D extends Comparable<D>>{
        // Outer Sort Call
        public L<D> sort(L<D> l){ return recsort(l); }
        // Inner Sort Call for recursion
        public L<D> recsort(L<D> l){
            int len = l.length();
            if(len <= 1)return l;
            L.P<D> p = l.split(len/2);
            //p(" recsort["+Thread.currentThread().getId()+"]: "+l);
            return merge(recsort(p.lt), recsort(p.rt));
        }
        
        // Timing Result class
        class T{
            long mil;
            L<D> lst;
            T(long m, L<D> l){ mil = m; lst = l; }
            public String toString(){ return " MSec: "+mil; }//+" : "+lst; }
        }
        // Caculate Timing Results for List sorting
        public T timesort(L<D> l){
            // Make sure Java doesn't interrupt us...
            System.gc();Thread.yield();
            long tm = System.currentTimeMillis();
            L<D> r = sort(l);
            // Must be careful about argument evaluation order...
            return new T(System.currentTimeMillis()-tm, r);
        }
    }

    // Sort Using java.util.Arrays
    static class ASorter<D extends Comparable<D>> extends Sorter<D>{
        public T timesort(L<D> l, D[] a){
            a = l.toArray(a);
            System.gc();Thread.yield();
            long tm = System.currentTimeMillis();
            java.util.Arrays.sort(a);
            return new T(System.currentTimeMillis()-tm, make(a));
        }
    }
    
    // Parallel Sorter version
    static class PSorter<D extends Comparable<D>> extends Sorter<D>{
        // Outer Sort call splits into a seperate thread for the
        //   Left Split (half) of the list.
        public L<D> sort(L<D> l){
            int len = l.length();
            if(len <= 1)return l;
            L.P<D> p = l.split(len/2);
            Thrd lt = new Thrd(p.lt); lt.start();
            L<D> rt = recsort(p.rt);
            p = null;
            lt.waitFor();
            return merge(lt.res, rt);
        }
        
        // Thunkish class to support delayed sorting in a separate thread
        class Thrd extends Thread{
            L<D> lst, res;
            boolean fin = false;
            Thrd(L<D> l){ lst = l; res = null; }
            public void run(){ res = recsort(lst); done(); }
            synchronized void done(){ fin = true; this.notifyAll(); }
            synchronized void waitFor(){ try{ while(!fin)wait(); }catch(InterruptedException e){} }
        }
    }
    
    // Classic merge method
    static <D extends Comparable<D>> L<D> merge(L<D> l1, L<D> l2){
        if(l1.isEmpty())return l2;
        if(l2.isEmpty())return l1;
        if(l1.first().compareTo(l2.first()) <= 0)
            return merge(l1.rest(), l2).push(l1.first());
        return merge(l1, l2.rest()).push(l2.first());
    }
    
    // Functional Generic Lists with the typical methods
    static class L<D extends Comparable<D>>{
        // Inner class for Pair of Lists when Splitting
        static class P<D extends Comparable<D>>{
            L<D> lt, rt;
            P(L<D> l, L<D> r){ lt = l; rt = r;}
            public String toString(){ return "<"+lt+" :: "+rt+">"; }
        }
        boolean isEmpty(){ return true; }
        D first(){ throw new RuntimeException("L.first() Bad"); }
        L<D> rest(){ throw new RuntimeException("L.rest() Bad"); }
        int length(){ return 0; }
        L<D> reverse(){ return reverse(new L<D>()); }
        L<D> reverse(L<D> ac){ return ac; }
        L<D> push(D d){ return new C<D>(d, this); }
        L<D> append(L<D> l){ return l; }
        P<D> split(int k){ return split(k,new L<D>()); }
        P<D> split(int k, L<D> ac){ throw new RuntimeException("L.split() Bad"); }
        public String toString(){ return ""; }
        D[] toArray(D[] d){ return toArray(d, 0); }
        D[] toArray(D[] d, int i){ return d; }
    }
    static class C<D extends Comparable<D>> extends L<D>{
        D f;
        L<D> r;
        C(D ff, L<D> rr){ f = ff; r = rr; }
        boolean isEmpty(){ return false; }
        D first(){ return f; }
        L<D> rest(){ return r; }
        int length(){ return 1+r.length(); }
        L<D> reverse(L<D> ac){ return r.reverse(ac.push(f)); }
        L<D> append(L<D> l){ return r.append(l).push(f); }
        P<D> split(int k, L<D> ac){ 
            return k==0?new P<D>(ac.reverse(),this):r.split(k-1, ac.push(f));    
        }
        public String toString(){ return f+" "+r; }
        D[] toArray(D[] d, int i){ d[i] = f; return r.toArray(d, i+1); }
    }
}