/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

import java.util.*;
import java.util.concurrent.*;

class CCBoxedLongSort {
    static final long NPS = (1000L * 1000 * 1000);
    static int THRESHOLD;
    static Long[] numbers;

    public static void main(String[] args) throws Exception {
        int n = 1 << 22;
        int reps = 30;
        int sreps = 2;
        try {
            if (args.length > 0)
                n = Integer.parseInt(args[0]);
            if (args.length > 1)
                reps = Integer.parseInt(args[1]);
        }
        catch (Exception e) {
            System.out.println("Usage: java CCC n reps");
            return;
        }

        numbers = new Long[n];
        for (int i = 0; i < n; ++i)
            numbers[i] = Long.valueOf(i);

        int thr = ((n + 7) >>> 3) / ForkJoinPool.getCommonPoolParallelism();
        THRESHOLD = (thr <= 1 << 13)? 1 << 13 : thr;

        System.out.println("Threshold = " + THRESHOLD);

        Object[] a = new Object[n];
        ForkJoinPool pool = ForkJoinPool.commonPool();
        seqTest(a, n, 1);
        System.out.println(pool);
        parTest(a, n, reps);
        System.out.println(pool);
        seqTest(a, n, 2);
        System.out.println(pool);
    }

    static void seqTest(Object[] a, int n, int reps) {
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            new RandomRepacker(null, numbers, a, 0, n, n).invoke();
            long last = System.nanoTime();
            java.util.Arrays.sort(a);
            long now = System.nanoTime();
            double total = (double)(now - start) / NPS;
            double elapsed = (double)(now - last) / NPS;
            System.out.printf("Arrays.sort   time:  %7.3f total %9.3f\n",
                              elapsed, total);
            new OrderChecker(null, a, 0, n, n).invoke();
        }
    }

    static void parTest(Object[] a, int n, int reps) throws Exception {
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            new RandomRepacker(null, numbers, a, 0, n, n).invoke();
            long last = System.nanoTime();
            new Sorter(null, a, new Object[n], 0, n).invoke();
            long now = System.nanoTime();
            double total = (double)(now - start) / NPS;
            double elapsed = (double)(now - last) / NPS;
            System.out.printf("Parallel sort time:  %7.3f total %9.3f\n",
                              elapsed, total);
            new OrderChecker(null, a, 0, n, n).invoke();
        }
    }


    /*
     * Merge sort alternates placing elements in the given array vs
     * the workspace array. To make sure the final elements are in the
     * given array, we descend in double steps.  So we need some
     * little tasks to serve as the place holders for triggering the
     * merges and re-merges. These don't need to keep track of the
     * arrays, and are never themselves forked, so are mostly empty.
     */
    static final class Subsorter extends CountedCompleter<Void> {
        Subsorter(CountedCompleter<?> p) { super(p); }
        public final void compute() { }
    }

    static final class Comerger extends CountedCompleter<Void> {
        final Merger merger;
        Comerger(Merger merger) {
            super(null, 1);
            this.merger = merger;
        }
        public final void compute() { }
        public final void onCompletion(CountedCompleter<?> t) {
            merger.compute();
        }
    }

    static final class Merger extends CountedCompleter<Void> {
        final Object[] a; final Object[] w;
        final int lo; final int ln; final int ro; final int rn; final int wo;
        Merger(CountedCompleter<?> par,
               Object[] a, Object[] w, int lo, int ln, int ro, int rn, int wo) {
            super(par);
            this.a = a;    this.w = w;
            this.lo = lo;  this.ln = ln;
            this.ro = ro;  this.rn = rn;
            this.wo = wo;
        }

        /**
         * Merge left and right by splitting left in half,
         * and finding index of right closest to split point.
         */
        public final void compute() {
            int l = this.lo, ln = this.ln;
            int r = this.ro, rn = this.rn;
            Object[] a = this.a;
            for (;;) {
                int lh = ln >>> 1;
                Comparable<Object> s = (Comparable<Object>) a[l + lh];
                int rh = rn;
                for (int rl = 0; rl < rh;) {
                    int rm = (rl + rh) >>> 1;
                    if (s.compareTo(a[r + rm]) > 0)
                        rl = rm + 1;
                    else
                        rh = rm;
                }
                if (lh + rh <= THRESHOLD || (ln - lh) + (rn - rh) <= THRESHOLD)
                    break;
                addToPendingCount(1);
                new Merger(this, a, w, l + lh, ln - lh, 
                           r + rh, rn - rh, wo + lh + rh).fork();
                rn = rh;
                ln = lh;
            }
            merge(l + ln, r + rn);
        }

        final void merge(int lf, int rf) {
            int l = this.lo, r = this.ro, k = this.wo;
            Object[] a = this.a, w = this.w;
            while (l < lf && r < rf) {
                Object t, ar; Comparable<Object> al;
                if ((al = (Comparable<Object>)a[l]).compareTo(ar = a[r]) <= 0) {
                    t = al; l++;
                }
                else {
                    t = ar; r++;
                }
                w[k++] = t;
            }
            if (r < rf)
                System.arraycopy(a, r, w, k, rf - r);
            else if (l < lf)
                System.arraycopy(a, l, w, k, lf - l);
            tryComplete();
        }
    }

    static final class Sorter extends CountedCompleter<Void> {
        final Object[] a;
        final Object[] w;
        final int origin;
        final int size;
        Sorter(CountedCompleter<?> par, Object[] a, Object[] w, int origin, int n) {
            super(par);
            this.a = a; this.w = w; this.origin = origin; this.size = n;
        }

        public final void compute() {
            int l = this.origin;
            int n = this.size;
            Object[] a = this.a;
            Object[] w = this.w;
            CountedCompleter<?> s = this;
            while (n > THRESHOLD) {
                int h = n >>> 1, q = n >>> 2, u = h + q;
                int lq = l + q, lh = l + h, lu = l + u;
                int nh = n - h, nu = n - u, hq = h - q;
                Comerger fc =
                    new Comerger(new Merger(s, w, a, l, h, lh, nh, l));
                Comerger rc =
                    new Comerger(new Merger(fc, a, w, lh, q, lu, nu, lh));
                Comerger lc =
                    new Comerger(new Merger(fc, a, w, l, q, lq, hq, l));
                Sorter su = new Sorter(rc, a, w, lu, nu);
                Sorter sh = new Sorter(rc, a, w, lh, q);
                Sorter sq = new Sorter(lc, a, w, lq, hq);
                su.fork();
                sh.fork();
                sq.fork();
                s = new Subsorter(lc);
                n = q;
            }
            quickSort(a, l, l+n-1);
            s.tryComplete();
        }

        static final int QUICKSORT_INSERTION_THRESHOLD = 8;

        static void quickSort(Object[] a, int lo, int hi) {
            for (;;) {
                if (hi - lo <= QUICKSORT_INSERTION_THRESHOLD) {
                    for (int i = lo; i < hi; i++) {
                        int j = i;
                        Comparable t = (Comparable)a[i + 1];
                        while (t.compareTo(a[j]) < 0) {
                            a[j+1] = a[j];
                            if (--j < lo)
                                break;
                        }
                        a[j+1] = t;
                    }
                    return;
                }
                
                int mid = (lo + hi) >>> 1;
                Object c;
                if (((Comparable)(c = a[lo])).compareTo(a[mid]) > 0) {
                    a[lo] = a[mid]; a[mid] = c;
                }
                if (((Comparable)(c = a[mid])).compareTo(a[hi]) > 0) {
                    a[mid] = a[hi]; a[hi] = c;
                    if (((Comparable)(c = a[lo])).compareTo(a[mid]) > 0) {
                        a[lo] = a[mid]; a[mid] = c;
                    }
                }
                
                Comparable pivot = (Comparable)a[mid];
                int left = lo + 1;
                int right = hi-1;
                for (;;) {
                    while (pivot.compareTo(a[right]) < 0)
                        --right;
                    while (left < right && pivot.compareTo(a[left]) >= 0)
                        ++left;
                    if (left < right) {
                        Object t = a[left]; a[left] = a[right]; a[right] = t;
                        --right;
                    }
                    else break;
                }
                
                if (left - lo <= hi - right) {
                    quickSort(a, lo, left);
                    lo = left + 1;
                }
                else {
                    quickSort(a, right, hi);
                    hi = left;
                }
            }
        }
    }


    static void checkSorted(Object[] a) {
        int n = a.length;
        long x = ((Long)a[0]).longValue(), y;
        for (int i = 0; i < n - 1; i++) {
            if (x > (y = ((Long)a[i+1]).longValue()))
                throw new Error("Unsorted at " + i + ": " + x + " / " + y);
            x = y;
        }
    }

    static final class RandomRepacker extends CountedCompleter<Void> {
        final Long[] src;
        final Object[] dst;
        final int lo, hi, size;
        RandomRepacker(CountedCompleter<?> par, Long[] src, Object[] dst,
                       int lo, int hi, int size) {
            super(par);
            this.src = src; this.dst = dst;
            this.lo = lo; this.hi = hi; this.size = size;
        }

        public final void compute() {
            Long[] s = src;
            Object[] d = dst;
            int l = lo, h = hi, n = size;
            while (h - l > THRESHOLD >>> 1) {
                int m = (l + h) >>> 1;
                addToPendingCount(1);
                new RandomRepacker(this, s, d, m, h, n).fork();
                h = m;
            }
            ThreadLocalRandom rng = ThreadLocalRandom.current();
            Object dl = d[l];
            int m = (dl == null)? h : rng.nextInt(l, h);
            for (int i = l; i < m; ++i)
                d[i] = s[rng.nextInt(n)];
            if (dl != null) {
                Object dm = s[m];
                for (int i = m + 1; i < h; ++i)
                    d[i] = dm;
            }
            tryComplete();
        }
    }

    static final class OrderChecker extends CountedCompleter<Void> {
        final Object[] array;
        final int lo, hi, size;
        OrderChecker(CountedCompleter<?> par, Object[] a, int lo, int hi, int size) {
            super(par);
            this.array = a;
            this.lo = lo; this.hi = hi; this.size = size;
        }

        public final void compute() {
            Object[] a = this.array;
            int l = lo, h = hi, n = size;
            while (h - l > THRESHOLD) {
                int m = (l + h) >>> 1;
                addToPendingCount(1);
                new OrderChecker(this, a, m, h, n).fork();
                h = m;
            }
            int bound = h < n ? h : n - 1;
            int i = l;
            long x = ((Long)a[i]).longValue(), y;
            while (i < bound) {
                if (x > (y = ((Long)a[++i]).longValue()))
                    throw new Error("Unsorted " + x + " / " + y);
                x = y;
            }
            tryComplete();
        }
    }

}