import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class MultiThreadedMergeSort4 {

    public Comparable array[];

    public MultiThreadedMergeSort4(Comparable array[]) {
        this.array = array;
    }

    public void sort() {
        ForkJoinPool pool = new ForkJoinPool();
        RecursiveAction start = new Sorter(0, array.length - 1);
        pool.invoke(start);
    }

    class Sorter extends RecursiveAction {
        public int left;
        public int right;

        public Sorter(int left, int right) {
            this.left = left;
            this.right = right;
        }

        protected void compute() {
            int i = left;
            int j = right;
            Comparable tmp;
            Comparable mid = array[(left + right) / 2];

            while (i <= j) {
                while (array[i].compareTo(mid) < 0) {
                    i++;
                }
                while (array[j].compareTo(mid) > 0) {
                    j--;
                }

                if (i <= j) {
                    tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                    i++;
                    j--;
                }
            }

            Sorter leftTask = null;
            Sorter rightTask = null;

            if (left < i - 1) {
                leftTask = new Sorter(left, i - 1);
            }
            if (i < right) {
                rightTask = new Sorter(i, right);
            }

            if (right - left > 2) {
                if (leftTask != null && rightTask != null) {
                    invokeAll(leftTask, rightTask);
                } else if (leftTask != null) {
                    invokeAll(leftTask);
                } else if (rightTask != null) {
                    invokeAll(rightTask);
                }
            } else {
                if (leftTask != null) {
                    leftTask.compute();
                }
                if (rightTask != null) {
                    rightTask.compute();
                }
            }
        }
    }
}