changeset 3271:215458300e18

Initial load of parallelSort support in FJUtils. Support for byte -> int, plus Comparable, and Object+Comparator ParallelSorting functional test is a mirror of the Arrays.sort Sorting test
author dholmes
date Mon, 14 Feb 2011 13:16:29 +1000
parents 73ca5d37cf1f
children 24a242400143
files src/share/classes/java/util/concurrent/ForkJoinUtils.java test/java/util/concurrent/forkjoin/ParallelSorting.java
diffstat 2 files changed, 2747 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/util/concurrent/ForkJoinUtils.java	Mon Feb 14 13:16:29 2011 +1000
@@ -0,0 +1,745 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * Portions derived from the extra166y package,
+ * 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/licenses/publicdomain
+ */
+
+package java.util.concurrent;
+
+import java.util.Arrays;
+import java.util.Comparator;
+import java.lang.reflect.Array;
+
+public final class ForkJoinUtils {
+
+    private ForkJoinUtils() {}; // no construction
+
+    /** The ForJoinPool we use for submissions by default */
+    static final ForkJoinPool ex;
+
+    /** The minimum granularity used by the sorting algorithm (eg minimum
+     *  sub-array length to partition further). A value of 0 indicates
+     *  to apply no minimum.
+    */
+    static final int MIN_GRAN;
+
+    static {
+	// to-do: access properties/config that controls how the
+	//        default pool is constructed
+	// Supports parallelism level initially
+
+	int parallelism = Runtime.getRuntime().availableProcessors();
+	
+	// to-do: add doPrivileged block?
+	String sParallelism = 
+	    System.getProperty("java.util.concurrent.FJPool.parallelism");
+	String sMinGran = 
+	    System.getProperty("java.util.concurrent.FJPool.minGran");
+
+	int minGran = 0;
+	try {
+	    if (sParallelism != null) {
+		int temp = Integer.parseInt(sParallelism);
+		if (temp > 0)
+		    parallelism = temp;
+	    }
+	    if (sMinGran != null) {
+		int temp = Integer.parseInt(sMinGran);
+		if (temp > 0)
+		    minGran = temp;
+	    }
+	}
+	catch (NumberFormatException _ignore) {}
+
+	MIN_GRAN = minGran;
+
+	// to-do: possibly lazy-initialize with holder idiom
+	ex = new ForkJoinPool();
+    }
+
+    public static ForkJoinPool defaultFJPool() {
+	return ex;
+    }
+
+
+    static void Unimplemented() {
+	throw new UnsupportedOperationException();
+    }
+
+    public static byte[] parallelSort(byte[] arr) {
+	return parallelSort(arr, 0, arr.length);
+    }
+
+    public static byte[] parallelSort(byte[] arr, int fromIndex, int toIndex) {
+	rangeCheck(arr.length, fromIndex, toIndex);
+	return (byte[]) primitiveSort(arr, arr.length, fromIndex, toIndex, BYTE);
+    }
+
+    public static char[] parallelSort(char[] arr) {
+	return parallelSort(arr, 0, arr.length);
+    }
+
+    public static char[] parallelSort(char[] arr, int fromIndex, int toIndex) {
+	rangeCheck(arr.length, fromIndex, toIndex);
+	return (char[]) primitiveSort(arr, arr.length, fromIndex, toIndex, CHAR);
+    }
+
+    public static short[] parallelSort(short[] arr) {
+	return parallelSort(arr, 0, arr.length);
+    }
+
+    public static short[] parallelSort(short[] arr, int fromIndex, int toIndex) {
+	rangeCheck(arr.length, fromIndex, toIndex);
+	return (short[]) primitiveSort(arr, arr.length, fromIndex, toIndex, SHORT);
+    }
+
+    public static long[] parallelSort(long[] arr) {
+	return parallelSort(arr, 0, arr.length);
+    }
+
+    public static long[] parallelSort(long[] arr, int fromIndex, int toIndex) {
+	rangeCheck(arr.length, fromIndex, toIndex);
+	Unimplemented();
+	return arr;
+    }
+
+    public static float[] parallelSort(float[] arr) {
+	return parallelSort(arr, 0, arr.length);
+    }
+
+    public static float[] parallelSort(float[] arr, int fromIndex, int toIndex) {
+	rangeCheck(arr.length, fromIndex, toIndex);
+	Unimplemented();
+	return arr;
+    }
+
+    public static double[] parallelSort(double[] arr) {
+	return parallelSort(arr, 0, arr.length);
+    }
+
+    public static double[] parallelSort(double[] arr, int fromIndex, int toIndex) {
+	rangeCheck(arr.length, fromIndex, toIndex);
+	Unimplemented();
+	return arr;
+    }
+
+
+    public static int[] parallelSort(int[] arr) {
+	return parallelSort(arr, 0, arr.length);
+    }
+
+    public static int[] parallelSort(int[] arr, int fromIndex, int toIndex) {
+	rangeCheck(arr.length, fromIndex, toIndex);
+	int origin = fromIndex;
+	int fence = toIndex;
+	int nelements = fence - origin;
+	// To-DO: we should only need a working array as large as the subarray
+	//        to be sorted, but the logic assumes that indices in the two
+	//        arrays always line-up
+	int[] ws = new int[arr.length];
+	int gran = getThreshold(nelements);
+	FJIntSorter task = new FJIntSorter(arr, ws, origin, nelements, gran);
+	try {
+	    ex.invoke(task);
+	}
+	catch (RuntimeException | Error ex) {
+	    throw new RuntimeException("Computation failed", ex);
+	}
+	return arr;
+    }
+
+    public static <T extends Comparable<T>> 
+			     T[] parallelSort(T[] arr) {
+	return parallelSort(arr, 0, arr.length);
+    }
+
+
+    public static <T extends Comparable<T>> 
+			     T[] parallelSort(T[] arr, int fromIndex, int toIndex) {
+	rangeCheck(arr.length, fromIndex, toIndex);
+	int origin = fromIndex;
+	int fence = toIndex;
+	int nelements = fence - origin;
+	Class<?> tc = arr.getClass().getComponentType();
+	// To-DO: we should only need a working array as large as the subarray
+	//        to be sorted, but the logic assumes that indices in the two
+	//        arrays always line-up
+        Comparable<T>[] ws = (Comparable<T>[])Array.newInstance(tc, arr.length);
+	int gran = getThreshold(nelements);
+	FJOCSorter<T> task = new FJOCSorter<T>(arr, ws, origin, nelements, gran);
+	try {
+	    ex.invoke(task);
+	}
+	catch (RuntimeException | Error ex) {
+	    throw new RuntimeException("Computation failed", ex);
+	}
+	return arr;
+    }
+
+    public static <T> T[] parallelSort(T[] arr, Comparator<T> cmp) {
+	return parallelSort(arr, 0, arr.length, cmp);
+    }
+
+    public static <T> T[] parallelSort(T[] arr, int fromIndex, int toIndex, 
+				       Comparator<T> cmp) {
+	rangeCheck(arr.length, fromIndex, toIndex);
+	Unimplemented();
+	return arr;
+    }
+
+
+    private static Object primitiveSort(Object arr, int arrlength, 
+					int fromIndex, int toIndex, int tag) {
+	int origin = fromIndex;
+	int fence = toIndex;
+	int nelements = fence - origin;
+	Class<?> tc = arr.getClass().getComponentType();
+	// To-DO: we should only need a working array as large as the subarray
+	//        to be sorted, but the logic assumes that indices in the two
+	//        arrays always line-up
+        Object ws  = Array.newInstance(tc, arrlength);
+	int gran = getThreshold(nelements);
+	FJPrimSorter task = new FJPrimSorter(arr, ws, origin, nelements, gran, tag);
+	try {
+	    ex.invoke(task);
+	}
+	catch (RuntimeException | Error ex) {
+	    throw new RuntimeException("Computation failed", ex);
+	}
+	return arr;
+    }
+
+
+    /**
+     * Sorter classes based mainly on CilkSort
+     * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
+     * Basic algorithm:
+     * if array size is small, just use a sequential quicksort
+     *         Otherwise:
+     *         1. Break array in half.
+     *         2. For each half,
+     *             a. break the half in half (i.e., quarters),
+     *             b. sort the quarters
+     *             c. merge them together
+     *         3. merge together the two halves.
+     *
+     * One reason for splitting in quarters is that this guarantees
+     * that the final sort is in the main array, not the workspace
+     * array.  (workspace and main swap roles on each subsort step.)
+     * Leaf-level sorts use a Sequential quicksort, that in turn uses
+     * insertion sort if under threshold.  Otherwise it uses median of
+     * three to pick pivot, and loops rather than recurses along left
+     * path.
+     *
+     */
+    static final class FJIntSorter extends RecursiveAction {
+        final int[] a;     // array to be sorted.
+        final int[] w;     // workspace for merge
+        final int origin;  // origin of the part of array we deal with
+        final int n;       // Number of elements in (sub)arrays.
+        final int gran;    // split control
+
+        FJIntSorter(int[] a, int[] w, int origin, int n, int gran) {
+            this.a = a; this.w = w; this.origin = origin; this.n = n;
+            this.gran = gran;
+	    if (debugEnabled) DEBUG("Construct: %s", this);
+        }
+	public String toString() {
+	    return String.format("FJIntSorter:[a.length=%d, w.length=%d, origin=%d, n=%d, gran=%d]", a.length, w.length, origin, n, gran);
+	}
+        public void compute() {
+	    if (debugEnabled) DEBUG("Compute: %s", this);
+            int l = origin;
+            int g = gran;
+            if (n > g) {
+                int h = n >>> 1; // half
+                int q = n >>> 2; // lower quarter index
+                int u = h + q;   // upper quarter
+                FJSubSorter ls = new FJSubSorter
+                    (new FJIntSorter(a, w, l,   q,   g),
+                     new FJIntSorter(a, w, l+q, h-q, g),
+                     new FJIntMerger(a, w, l,   q,
+                                   l+q, h-q, l, g, null));
+                FJSubSorter rs = new FJSubSorter
+                    (new FJIntSorter(a, w, l+h, q,   g),
+                     new FJIntSorter(a, w, l+u, n-u, g),
+                     new FJIntMerger(a, w, l+h, q,
+                                   l+u, n-u, l+h, g, null));
+                rs.fork();
+                ls.compute();
+                if (rs.tryUnfork()) rs.compute(); else rs.join();
+                new FJIntMerger(w, a, l, h,
+                              l+h, n-h, l, g, null).compute();
+            }
+            else
+                Arrays.sort(a, l, l+n);
+        }
+    }
+
+    static final class FJPrimSorter extends RecursiveAction {
+        final Object a;     // array to be sorted.
+        final Object w;     // workspace for merge
+        final int origin;  // origin of the part of array we deal with
+        final int n;       // Number of elements in (sub)arrays.
+        final int gran;    // split control
+	final int tag;     // primitive type tag
+
+        FJPrimSorter(Object a, Object w, int origin, int n, int gran, int tag) {
+            this.a = a; this.w = w; this.origin = origin; this.n = n;
+            this.gran = gran; this.tag = tag;
+        }
+        public void compute() {
+            int l = origin;
+            int g = gran;
+            if (n > g) {
+                int h = n >>> 1; // half
+                int q = n >>> 2; // lower quarter index
+                int u = h + q;   // upper quarter
+                FJSubSorter ls = new FJSubSorter
+                    (new FJPrimSorter(a, w, l,   q,   g, tag),
+                     new FJPrimSorter(a, w, l+q, h-q, g, tag),
+                     new FJPrimMerger(a, w, l,   q,
+                                   l+q, h-q, l, g, null, tag));
+                FJSubSorter rs = new FJSubSorter
+                    (new FJPrimSorter(a, w, l+h, q,   g, tag),
+                     new FJPrimSorter(a, w, l+u, n-u, g, tag),
+                     new FJPrimMerger(a, w, l+h, q,
+                                   l+u, n-u, l+h, g, null, tag));
+                rs.fork();
+                ls.compute();
+                if (rs.tryUnfork()) rs.compute(); else rs.join();
+                new FJPrimMerger(w, a, l, h,
+                              l+h, n-h, l, g, null, tag).compute();
+            }
+            else {
+		switch (tag) {
+		case BYTE:
+		    Arrays.sort((byte[])a, l, l+n); break;
+		case CHAR:
+		    Arrays.sort((char[])a, l, l+n); break;
+		case SHORT:
+		    Arrays.sort((short[])a, l, l+n); break;
+		case INT:
+		    Arrays.sort((int[])a, l, l+n); break;
+		default:
+		    throw new Error("invalid tag: " + tag);
+		}
+	    }
+
+        }
+    }
+
+    static final class FJOCSorter<T> extends RecursiveAction {
+        final Comparable<T>[] a; final Comparable<T>[] w;
+        final int origin; final int n; final int gran;
+        FJOCSorter(Comparable<T>[] a, Comparable<T>[] w,
+                   int origin, int n, int gran) {
+            this.a = a; this.w = w; this.origin = origin; this.n = n;
+            this.gran = gran;
+        }
+        public void compute() {
+            int l = origin;
+            int g = gran;
+            if (n > g) {
+                int h = n >>> 1;
+                int q = n >>> 2;
+                int u = h + q;
+                FJSubSorter ls = new FJSubSorter<>
+                    (new FJOCSorter<>(a, w, l,   q,   g),
+                     new FJOCSorter<>(a, w, l+q, h-q, g),
+                     new FJOCMerger<>(a, w, l,   q,
+                                   l+q, h-q, l, g, null));
+                FJSubSorter rs = new FJSubSorter<>
+                    (new FJOCSorter<>(a, w, l+h, q,   g),
+                     new FJOCSorter<>(a, w, l+u, n-u, g),
+                     new FJOCMerger<>(a, w, l+h, q,
+                                   l+u, n-u, l+h, g, null));
+                rs.fork();
+                ls.compute();
+                if (rs.tryUnfork()) rs.compute(); else rs.join();
+                new FJOCMerger<>(w, a, l, h,
+                               l+h, n-h, l, g, null).compute();
+            }
+            else
+                Arrays.sort(a, l, l+n);
+        }
+    }
+
+
+    /** Utility class to sort half a partitioned array */
+    static final class FJSubSorter extends RecursiveAction {
+        final RecursiveAction left;
+        final RecursiveAction right;
+        final RecursiveAction merger;
+        FJSubSorter(RecursiveAction left, RecursiveAction right,
+                    RecursiveAction merger) {
+            this.left = left; this.right = right; this.merger = merger;
+        }
+        public void compute() {
+            right.fork();
+            left.invoke();
+            right.join();
+            merger.invoke();
+        }
+    }
+
+    /**
+     * Perform merging for FJSorter. If big enough, splits Left
+     * partition in half; finds the greatest point in Right partition
+     * less than the beginning of the second half of Left via binary
+     * search; and then, in parallel, merges left half of Left with
+     * elements of Right up to split point, and merges right half of
+     * Left with elements of R past split point. At leaf, it just
+     * sequentially merges. This is all messy to code; sadly we need
+     * six versions.
+     */
+    static final class FJIntMerger extends RecursiveAction {
+        final int[] a; final int[] w;
+        final int lo; final int ln; final int ro; final int rn; final int wo;
+        final int gran;
+        final FJIntMerger next;
+        FJIntMerger(int[] a, int[] w, int lo,
+                   int ln, int ro, int rn, int wo,
+                   int gran, FJIntMerger next) {
+            this.a = a;    this.w = w;
+            this.lo = lo;  this.ln = ln;
+            this.ro = ro;  this.rn = rn;
+            this.wo = wo;
+            this.gran = gran;
+            this.next = next;
+	    if (debugEnabled) DEBUG("Construct: %s", this);
+        }
+	public String toString() {
+	    return String.format("FJIntMerge:[a.length=%d, w.length=%d, lo=%d, ro=%d, wo=%d, ln=%d, rn=%d, gran=%d]", a.length, w.length, lo, ro, wo, ln, rn, gran);
+	}
+        public void compute() {
+	    if (debugEnabled) DEBUG("Compute: %s", this);
+            FJIntMerger rights = null;
+            int nleft = ln;
+            int nright = rn;
+            while (nleft > gran) {
+                int lh = nleft >>> 1;
+                int splitIndex = lo + lh;
+                int split = a[splitIndex];
+                int rl = 0;
+                int rh = nright;
+                while (rl < rh) {
+                    int mid = (rl + rh) >>> 1;
+                    if (split <= a[ro + mid])
+                        rh = mid;
+                    else
+                        rl = mid + 1;
+                }
+                (rights = new FJIntMerger
+                 (a, w, splitIndex, nleft-lh, ro+rh,
+                  nright-rh, wo+lh+rh, gran, rights)).fork();
+                nleft = lh;
+                nright = rh;
+            }
+
+            int l = lo;
+            int lFence = lo + nleft;
+            int r = ro;
+            int rFence = ro + nright;
+            int k = wo;
+            while (l < lFence && r < rFence) {
+                int al = a[l];
+                int ar = a[r];
+                int t;
+                if (al <= ar) {++l; t=al;} else {++r; t = ar;}
+                w[k++] = t;
+            }
+            while (l < lFence)
+                w[k++] = a[l++];
+            while (r < rFence) {
+                w[k++] = a[r++];
+	    }
+            while (rights != null) {
+                if (rights.tryUnfork())
+                    rights.compute();
+                else
+                    rights.join();
+                rights = rights.next;
+            }
+        }
+    }
+
+    static final class FJPrimMerger extends RecursiveAction {
+        final Object a; final Object w;
+        final int lo; final int ln; final int ro; final int rn; final int wo;
+        final int gran;
+        final FJPrimMerger next;
+	final int tag;
+        FJPrimMerger(Object a, Object w, int lo,
+                   int ln, int ro, int rn, int wo,
+                   int gran, FJPrimMerger next, int tag) {
+            this.a = a;    this.w = w;
+            this.lo = lo;  this.ln = ln;
+            this.ro = ro;  this.rn = rn;
+            this.wo = wo;
+            this.gran = gran;
+            this.next = next;
+	    this.tag = tag;
+        }
+        public void compute() {
+            FJPrimMerger rights = null;
+            int nleft = ln;
+            int nright = rn;
+            while (nleft > gran) {
+                int lh = nleft >>> 1;
+                int splitIndex = lo + lh;
+                int split = getElemAt(a,splitIndex);
+                int rl = 0;
+                int rh = nright;
+                while (rl < rh) {
+                    int mid = (rl + rh) >>> 1;
+                    if (split <= getElemAt(a,ro + mid))
+                        rh = mid;
+                    else
+                        rl = mid + 1;
+                }
+                (rights = new FJPrimMerger
+                 (a, w, splitIndex, nleft-lh, ro+rh,
+                  nright-rh, wo+lh+rh, gran, rights, tag)).fork();
+                nleft = lh;
+                nright = rh;
+            }
+
+            int l = lo;
+            int lFence = lo + nleft;
+            int r = ro;
+            int rFence = ro + nright;
+            int k = wo;
+            while (l < lFence && r < rFence) {
+                int al = getElemAt(a,l);
+                int ar = getElemAt(a,r);
+                int t;
+                if (al <= ar) {++l; t=al;} else {++r; t = ar;}
+                setElemAt(w, k++, t);
+            }
+            while (l < lFence)
+		setElemAt(w, k++, getElemAt(a,l++));
+            while (r < rFence) 
+		setElemAt(w, k++, getElemAt(a,r++));
+            while (rights != null) {
+                if (rights.tryUnfork())
+                    rights.compute();
+                else
+                    rights.join();
+                rights = rights.next;
+            }
+        }
+
+	final int getElemAt(Object a, int index) {
+	    long offset = bases[tag] + index * scales[tag];
+	    switch (tag) {
+	    case BYTE:
+		return UNSAFE.getByte(a, offset);
+	    case CHAR:
+		return UNSAFE.getChar(a, offset);
+	    case SHORT:
+		return UNSAFE.getShort(a, offset);
+	    case INT:
+		return UNSAFE.getInt(a, offset);
+	    default:
+		throw new Error("invalid tag: " + tag);
+	    }
+	}
+
+	final void setElemAt(Object a, int index, int v) {
+	    long offset = bases[tag] + index * scales[tag];
+	    switch (tag) {
+	    case BYTE:
+		UNSAFE.putByte(a, offset, (byte)v); break;
+	    case CHAR:
+		UNSAFE.putChar(a, offset, (char)v); break;
+	    case SHORT:
+		UNSAFE.putShort(a, offset, (short)v); break;
+	    case INT:
+		UNSAFE.putInt(a, offset, v); break;
+	    default:
+		throw new Error("invalid tag: " + tag);
+	    }
+	}
+	
+    }
+
+
+    static final class FJOCMerger<T> extends RecursiveAction {
+        final Comparable<T>[] a; final Comparable<T>[] w;
+        final int lo; final int ln; final int ro;  final int rn; final int wo;
+        final int gran;
+        final FJOCMerger<T> next;
+        FJOCMerger(Comparable<T>[] a, Comparable<T>[] w, int lo,
+                   int ln, int ro, int rn, int wo,
+                   int gran, FJOCMerger<T> next) {
+            this.a = a;    this.w = w;
+            this.lo = lo;  this.ln = ln; this.ro = ro; this.rn = rn;
+            this.wo = wo;
+            this.gran = gran;
+            this.next = next;
+        }
+
+        public void compute() {
+            FJOCMerger<T> rights = null;
+            int nleft = ln;
+            int nright = rn;
+            while (nleft > gran) {
+                int lh = nleft >>> 1;
+                int splitIndex = lo + lh;
+                Comparable<T> split = a[splitIndex];
+                int rl = 0;
+                int rh = nright;
+                while (rl < rh) {
+                    int mid = (rl + rh) >>> 1;
+                    if (split.compareTo((T)a[ro + mid]) <= 0)
+                        rh = mid;
+                    else
+                        rl = mid + 1;
+                }
+                (rights = new FJOCMerger<>
+                 (a, w, splitIndex, nleft-lh, ro+rh,
+                  nright-rh, wo+lh+rh, gran, rights)).fork();
+                nleft = lh;
+                nright = rh;
+            }
+
+            int l = lo;
+            int lFence = lo + nleft;
+            int r = ro;
+            int rFence = ro + nright;
+            int k = wo;
+            while (l < lFence && r < rFence) {
+                Comparable<T> al = a[l];
+                Comparable<T> ar = a[r];
+                Comparable<T> t;
+                if (al.compareTo((T)ar) <= 0) {++l; t=al;} else {++r; t=ar; }
+                w[k++] = t;
+            }
+            while (l < lFence)
+                w[k++] = a[l++];
+            while (r < rFence)
+                w[k++] = a[r++];
+            while (rights != null) {
+                if (rights.tryUnfork())
+                    rights.compute();
+                else
+                    rights.join();
+                rights = rights.next;
+            }
+        }
+    }
+
+
+    /**
+     * Returns size threshold for splitting into subtask.  By
+     * default, uses about 8 times as many tasks as threads
+     *
+     * @param n number of elements in the array to be processed
+     */
+    static final int getThreshold(int n) {
+	int p = ex.getParallelism();
+	int t = (p > 1) ? (1 + n / (p << 3)) : n;
+	return t < MIN_GRAN ? MIN_GRAN : t;
+    }
+
+    /**
+     * Checks that {@code fromIndex} and {@code toIndex} are in
+     * the range and throws an appropriate exception, if they aren't.
+     */
+    private static void rangeCheck(int length, int fromIndex, int toIndex) {
+        if (fromIndex > toIndex) {
+            throw new IllegalArgumentException(
+                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+        }
+        if (fromIndex < 0) {
+            throw new ArrayIndexOutOfBoundsException(fromIndex);
+        }
+        if (toIndex > length) {
+            throw new ArrayIndexOutOfBoundsException(toIndex);
+        }
+    }
+
+    static final boolean debugEnabled = System.getProperty("DEBUG") != null;
+
+    static { System.out.printf("DEBUG state = %b%n", debugEnabled); }
+
+    private static void DEBUG(String msg, Object... args) {
+	if (debugEnabled) {
+	    System.out.format(msg, args);
+	    System.out.println();
+	}
+    }
+
+
+    // type tagging support
+    private static final int BYTE = 0;
+    private static final int CHAR = BYTE+1;
+    private static final int SHORT = CHAR+1;
+    private static final int INT = SHORT+1;
+    private static final int LONG = INT+1;
+    private static final int FLOAT = LONG+1;
+    private static final int DOUBLE = FLOAT+1;
+    private static final int NTYPES = DOUBLE+1;
+
+    private static final int[] bases = new int[NTYPES];
+    private static final int[] scales  = new int[NTYPES];
+    // Unsafe mechanics
+
+    private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
+    static {
+	bases[BYTE] =
+	    UNSAFE.arrayBaseOffset(byte[].class);
+	bases[CHAR] =
+	    UNSAFE.arrayBaseOffset(char[].class);
+	bases[SHORT] =
+	    UNSAFE.arrayBaseOffset(short[].class);
+	bases[INT] =
+	    UNSAFE.arrayBaseOffset(int[].class);
+	bases[LONG] =
+	    UNSAFE.arrayBaseOffset(long[].class);
+	bases[FLOAT] =
+	    UNSAFE.arrayBaseOffset(float[].class);
+	bases[DOUBLE] =
+	    UNSAFE.arrayBaseOffset(double[].class);
+
+	scales[BYTE] =
+	    UNSAFE.arrayIndexScale(byte[].class);
+	scales[CHAR] =
+	    UNSAFE.arrayIndexScale(char[].class);
+	scales[SHORT] =
+	    UNSAFE.arrayIndexScale(short[].class);
+	scales[INT] =
+	    UNSAFE.arrayIndexScale(int[].class);
+	scales[LONG] =
+	    UNSAFE.arrayIndexScale(long[].class);
+	scales[FLOAT] =
+	    UNSAFE.arrayIndexScale(float[].class);
+	scales[DOUBLE] =
+	    UNSAFE.arrayIndexScale(double[].class);
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/concurrent/forkjoin/ParallelSorting.java	Mon Feb 14 13:16:29 2011 +1000
@@ -0,0 +1,2002 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/* Adapted from test/java/util/Arrays/Sorting.java
+ *
+ * Where that test checks Arrays.sort against manual quicksort routines,
+ * this test checks parallelSort against either Arrays.sort or manual
+ * quicksort routines.
+ */
+
+/*
+ * @test
+ * @summary Exercise ForkJoinUtils.parallelSort
+ * @build ParallelSorting
+ * @run main Sorting -shortrun
+ *
+ * @author Vladimir Yaroslavskiy
+ * @author Jon Bentley
+ * @author Josh Bloch
+ */
+
+import java.util.Arrays;
+import java.util.Random;
+import java.io.PrintStream;
+import java.util.concurrent.ForkJoinUtils;
+
+public class ParallelSorting {
+    private static final PrintStream out = System.out;
+    private static final PrintStream err = System.err;
+
+    // Array lengths used in a long run (default)
+    private static final int[] LONG_RUN_LENGTHS = {
+        1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 };
+
+    // Array lengths used in a short run
+    private static final int[] SHORT_RUN_LENGTHS = {
+        1, 2, 3, 21, 55, 1000, 10000 };
+
+    // Random initial values used in a long run (default)
+    private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };
+
+    // Random initial values used in a short run
+    private static final long[] SHORT_RUN_RANDOMS = { 666 };
+
+    public static void main(String[] args) {
+        boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
+        long start = System.currentTimeMillis();
+
+        if (shortRun) {
+            testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
+        } else {
+            testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
+        }
+        long end = System.currentTimeMillis();
+
+        out.format("\nPASSED in %d sec.\n", Math.round((end - start) / 1E3));
+    }
+
+    private static void testAndCheck(int[] lengths, long[] randoms) {
+        testEmptyAndNullIntArray();
+//         testEmptyAndNullLongArray();
+        testEmptyAndNullShortArray();
+        testEmptyAndNullCharArray();
+	testEmptyAndNullByteArray();
+//         testEmptyAndNullFloatArray();
+//         testEmptyAndNullDoubleArray();
+
+        for (long random : randoms) {
+            reset(random);
+
+            for (int length : lengths) {
+                testAndCheckWithInsertionSort(length, random);
+            }
+            reset(random);
+
+            for (int length : lengths) {
+                testAndCheckWithCheckSum(length, random);
+            }
+            reset(random);
+
+            for (int length : lengths) {
+                testAndCheckWithScrambling(length, random);
+            }
+            reset(random);
+
+//             for (int length : lengths) {
+//                 testAndCheckFloat(length, random);
+//             }
+//             reset(random);
+
+//             for (int length : lengths) {
+//                 testAndCheckDouble(length, random);
+//             }
+//             reset(random);
+
+            for (int length : lengths) {
+                testAndCheckRange(length, random);
+            }
+            reset(random);
+
+            for (int length : lengths) {
+                testAndCheckSubArray(length, random);
+            }
+            reset(random);
+
+            for (int length : lengths) {
+                testStable(length, random);
+            }
+        }
+    }
+
+    private static void testEmptyAndNullIntArray() {
+        ourDescription = "Check empty and null array";
+        ForkJoinUtils.parallelSort(new int[] {});
+        ForkJoinUtils.parallelSort(new int[] {}, 0, 0);
+
+        try {
+            ForkJoinUtils.parallelSort((int[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                ForkJoinUtils.parallelSort((int[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("ForkJoinUtils.parallelSort(int[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("ForkJoinUtils.parallelSort(int[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullLongArray() {
+        ourDescription = "Check empty and null array";
+        ForkJoinUtils.parallelSort(new long[] {});
+        ForkJoinUtils.parallelSort(new long[] {}, 0, 0);
+
+        try {
+            ForkJoinUtils.parallelSort((long[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                ForkJoinUtils.parallelSort((long[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("ForkJoinUtils.parallelSort(long[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("ForkJoinUtils.parallelSort(long[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullShortArray() {
+        ourDescription = "Check empty and null array";
+        ForkJoinUtils.parallelSort(new short[] {});
+        ForkJoinUtils.parallelSort(new short[] {}, 0, 0);
+
+        try {
+            ForkJoinUtils.parallelSort((short[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                ForkJoinUtils.parallelSort((short[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("ForkJoinUtils.parallelSort(short[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("ForkJoinUtils.parallelSort(short[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullCharArray() {
+        ourDescription = "Check empty and null array";
+        ForkJoinUtils.parallelSort(new char[] {});
+        ForkJoinUtils.parallelSort(new char[] {}, 0, 0);
+
+        try {
+            ForkJoinUtils.parallelSort((char[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                ForkJoinUtils.parallelSort((char[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("ForkJoinUtils.parallelSort(char[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("ForkJoinUtils.parallelSort(char[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullByteArray() {
+        ourDescription = "Check empty and null array";
+        ForkJoinUtils.parallelSort(new byte[] {});
+        ForkJoinUtils.parallelSort(new byte[] {}, 0, 0);
+
+        try {
+            ForkJoinUtils.parallelSort((byte[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                ForkJoinUtils.parallelSort((byte[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("ForkJoinUtils.parallelSort(byte[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("ForkJoinUtils.parallelSort(byte[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullFloatArray() {
+        ourDescription = "Check empty and null array";
+        ForkJoinUtils.parallelSort(new float[] {});
+        ForkJoinUtils.parallelSort(new float[] {}, 0, 0);
+
+        try {
+            ForkJoinUtils.parallelSort((float[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                ForkJoinUtils.parallelSort((float[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("ForkJoinUtils.parallelSort(float[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("ForkJoinUtils.parallelSort(float[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullDoubleArray() {
+        ourDescription = "Check empty and null array";
+        ForkJoinUtils.parallelSort(new double[] {});
+        ForkJoinUtils.parallelSort(new double[] {}, 0, 0);
+
+        try {
+            ForkJoinUtils.parallelSort((double[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                ForkJoinUtils.parallelSort((double[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("ForkJoinUtils.parallelSort(double[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("ForkJoinUtils.parallelSort(double[]) shouldn't catch null array");
+    }
+
+    private static void testAndCheckSubArray(int length, long random) {
+        ourDescription = "Check sorting of subarray";
+        int[] golden = new int[length];
+        boolean newLine = false;
+
+        for (int m = 1; m < length / 2; m *= 2) {
+            newLine = true;
+            int fromIndex = m;
+            int toIndex = length - m;
+
+            prepareSubArray(golden, fromIndex, toIndex, m);
+            int[] test = golden.clone();
+
+            for (TypeConverter converter : TypeConverter.values()) {
+                out.println("Test 'subarray': " + converter +
+                   " length = " + length + ", fromIndex = " + m +
+			    ", toIndex =" +toIndex);
+                Object convertedGolden = converter.convert(golden);
+                Object convertedTest = converter.convert(test);
+                sortSubArray(convertedTest, fromIndex, toIndex);
+                checkSubArray(convertedTest, fromIndex, toIndex, m);
+            }
+        }
+        if (newLine) {
+            out.println();
+        }
+    }
+
+    private static void testAndCheckRange(int length, long random) {
+        ourDescription = "Check range check";
+        int[] golden = new int[length];
+
+        for (int m = 1; m < 2 * length; m *= 2) {
+            for (int i = 1; i <= length; i++) {
+                golden[i - 1] = i % m + m % i;
+            }
+            for (TypeConverter converter : TypeConverter.values()) {
+                out.println("Test 'range': " + converter +
+                   ", length = " + length + ", m = " + m);
+                Object convertedGolden = converter.convert(golden);
+                checkRange(convertedGolden, m);
+            }
+        }
+        out.println();
+    }
+
+    private static void testStable(int length, long random) {
+        ourDescription = "Check if sorting is stable";
+        Pair[] a = build(length);
+
+        out.println("Test 'stable': " + "random = " +  random +
+            ", length = " + length);
+        ForkJoinUtils.parallelSort(a);
+        checkSorted(a);
+        checkStable(a);
+    }
+
+    private static void checkSorted(Pair[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i].getKey() > a[i + 1].getKey()) {
+                failedSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
+            }
+        }
+    }
+
+    private static void checkStable(Pair[] a) {
+        for (int i = 0; i < a.length / 4; ) {
+            int key1 = a[i].getKey();
+            int value1 = a[i++].getValue();
+            int key2 = a[i].getKey();
+            int value2 = a[i++].getValue();
+            int key3 = a[i].getKey();
+            int value3 = a[i++].getValue();
+            int key4 = a[i].getKey();
+            int value4 = a[i++].getValue();
+
+            if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
+                failed("On position " + i + " keys are different " +
+                    key1 + ", " + key2 + ", " + key3 + ", " + key4);
+            }
+            if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
+                failed("Sorting is not stable at position " + i +
+                    ". Second values have been changed: " +  value1 + ", " +
+                    value2 + ", " + value3 + ", " + value4);
+            }
+        }
+    }
+
+    private static Pair[] build(int length) {
+        Pair[] a = new Pair[length * 4];
+
+        for (int i = 0; i < a.length; ) {
+            int key = ourRandom.nextInt();
+            a[i++] = new Pair(key, 1);
+            a[i++] = new Pair(key, 2);
+            a[i++] = new Pair(key, 3);
+            a[i++] = new Pair(key, 4);
+        }
+        return a;
+    }
+
+    private static final class Pair implements Comparable<Pair> {
+        Pair(int key, int value) {
+            myKey = key;
+            myValue = value;
+        }
+
+        int getKey() {
+            return myKey;
+        }
+
+        int getValue() {
+            return myValue;
+        }
+
+        public int compareTo(Pair pair) {
+            if (myKey < pair.myKey) {
+                return -1;
+            }
+            if (myKey > pair.myKey) {
+                return 1;
+            }
+            return 0;
+        }
+
+        @Override
+        public String toString() {
+            return "(" + myKey + ", " + myValue + ")";
+        }
+
+        private int myKey;
+        private int myValue;
+    }
+
+
+    private static void testAndCheckWithInsertionSort(int length, long random) {
+        if (length > 1000) {
+            return;
+        }
+        ourDescription = "Check sorting with insertion sort";
+        int[] golden = new int[length];
+
+        for (int m = 1; m < 2 * length; m *= 2) {
+            for (UnsortedBuilder builder : UnsortedBuilder.values()) {
+                builder.build(golden, m);
+                int[] test = golden.clone();
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test 'insertion sort': " + converter + " " +
+                        builder + "random = " +  random + ", length = " +
+                        length + ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    Object convertedTest1 = converter.convert(test);
+                    Object convertedTest2 = converter.convert(test);
+                    sort(convertedTest1);
+                    sortByInsertionSort(convertedTest2);
+                    compare(convertedTest1, convertedTest2);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckWithCheckSum(int length, long random) {
+        ourDescription = "Check sorting with check sum";
+        int[] golden = new int[length];
+
+        for (int m = 1; m < 2 * length; m *= 2) {
+            for (UnsortedBuilder builder : UnsortedBuilder.values()) {
+                builder.build(golden, m);
+                int[] test = golden.clone();
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test 'check sum': " + converter + " " +
+                        builder + "random = " +  random + ", length = " +
+                        length + ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    Object convertedTest = converter.convert(test);
+                    sort(convertedTest);
+                    checkWithCheckSum(convertedTest, convertedGolden);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckWithScrambling(int length, long random) {
+        ourDescription = "Check sorting with scrambling";
+        int[] golden = new int[length];
+
+        for (int m = 1; m <= 7; m++) {
+            if (m > length) {
+                break;
+            }
+            for (SortedBuilder builder : SortedBuilder.values()) {
+                builder.build(golden, m);
+                int[] test = golden.clone();
+                scramble(test);
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test 'scrambling': " + converter + " " +
+                       builder + "random = " +  random + ", length = " +
+                       length + ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    Object convertedTest = converter.convert(test);
+                    sort(convertedTest);
+                    compare(convertedTest, convertedGolden);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckFloat(int length, long random) {
+        ourDescription = "Check float sorting";
+        float[] golden = new float[length];
+        final int MAX = 10;
+        boolean newLine = false;
+
+        for (int a = 0; a <= MAX; a++) {
+            for (int g = 0; g <= MAX; g++) {
+                for (int z = 0; z <= MAX; z++) {
+                    for (int n = 0; n <= MAX; n++) {
+                        for (int p = 0; p <= MAX; p++) {
+                            if (a + g + z + n + p > length) {
+                                continue;
+                            }
+                            if (a + g + z + n + p < length) {
+                                continue;
+                            }
+                            for (FloatBuilder builder : FloatBuilder.values()) {
+                                out.println("Test 'float': random = " + random +
+                                   ", length = " + length + ", a = " + a +
+                                   ", g = " + g + ", z = " + z + ", n = " + n +
+                                   ", p = " + p);
+                                builder.build(golden, a, g, z, n, p);
+                                float[] test = golden.clone();
+                                scramble(test);
+                                sort(test);
+                                compare(test, golden, a, n, g);
+                            }
+                            newLine = true;
+                        }
+                    }
+                }
+            }
+        }
+        if (newLine) {
+            out.println();
+        }
+    }
+
+    private static void testAndCheckDouble(int length, long random) {
+        ourDescription = "Check double sorting";
+        double[] golden = new double[length];
+        final int MAX = 10;
+        boolean newLine = false;
+
+        for (int a = 0; a <= MAX; a++) {
+            for (int g = 0; g <= MAX; g++) {
+                for (int z = 0; z <= MAX; z++) {
+                    for (int n = 0; n <= MAX; n++) {
+                        for (int p = 0; p <= MAX; p++) {
+                            if (a + g + z + n + p > length) {
+                                continue;
+                            }
+                            if (a + g + z + n + p < length) {
+                                continue;
+                            }
+                            for (DoubleBuilder builder : DoubleBuilder.values()) {
+                                out.println("Test 'double': random = " + random +
+                                   ", length = " + length + ", a = " + a + ", g = " +
+                                   g + ", z = " + z + ", n = " + n + ", p = " + p);
+                                builder.build(golden, a, g, z, n, p);
+                                double[] test = golden.clone();
+                                scramble(test);
+                                sort(test);
+                                compare(test, golden, a, n, g);
+                            }
+                            newLine = true;
+                        }
+                    }
+                }
+            }
+        }
+        if (newLine) {
+            out.println();
+        }
+    }
+
+    private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            a[i] = 0xBABA;
+        }
+        for (int i = fromIndex; i < toIndex; i++) {
+            a[i] = -i + m;
+        }
+        for (int i = toIndex; i < a.length; i++) {
+            a[i] = 0xDEDA;
+        }
+    }
+
+    private static void scramble(int[] a) {
+        for (int i = 0; i < a.length * 7; i++) {
+            swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
+        }
+    }
+
+    private static void scramble(float[] a) {
+        for (int i = 0; i < a.length * 7; i++) {
+            swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
+        }
+    }
+
+    private static void scramble(double[] a) {
+        for (int i = 0; i < a.length * 7; i++) {
+            swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
+        }
+    }
+
+    private static void swap(int[] a, int i, int j) {
+        int t = a[i];
+        a[i] = a[j];
+        a[j] = t;
+    }
+
+    private static void swap(float[] a, int i, int j) {
+        float t = a[i];
+        a[i] = a[j];
+        a[j] = t;
+    }
+
+    private static void swap(double[] a, int i, int j) {
+        double t = a[i];
+        a[i] = a[j];
+        a[j] = t;
+    }
+
+    private static enum TypeConverter {
+        INT {
+            Object convert(int[] a) {
+                return a.clone();
+            }
+        },
+//         LONG {
+//             Object convert(int[] a) {
+//                 long[] b = new long[a.length];
+
+//                 for (int i = 0; i < a.length; i++) {
+//                     b[i] = (long) a[i];
+//                 }
+//                 return b;
+//             }
+//         },
+        BYTE {
+            Object convert(int[] a) {
+                byte[] b = new byte[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = (byte) a[i];
+                }
+                return b;
+            }
+        },
+        SHORT {
+            Object convert(int[] a) {
+                short[] b = new short[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = (short) a[i];
+                }
+                return b;
+            }
+        },
+        CHAR {
+            Object convert(int[] a) {
+                char[] b = new char[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = (char) a[i];
+                }
+                return b;
+            }
+        },
+//         FLOAT {
+//             Object convert(int[] a) {
+//                 float[] b = new float[a.length];
+
+//                 for (int i = 0; i < a.length; i++) {
+//                     b[i] = (float) a[i];
+//                 }
+//                 return b;
+//             }
+//         },
+//         DOUBLE {
+//             Object convert(int[] a) {
+//                 double[] b = new double[a.length];
+
+//                 for (int i = 0; i < a.length; i++) {
+//                     b[i] = (double) a[i];
+//                 }
+//                 return b;
+//             }
+//         },
+        INTEGER {
+            Object convert(int[] a) {
+                Integer[] b = new Integer[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = new Integer(a[i]);
+                }
+                return b;
+            }
+        };
+
+        abstract Object convert(int[] a);
+
+        @Override public String toString() {
+            String name = name();
+
+            for (int i = name.length(); i < 9; i++) {
+                name += " ";
+            }
+            return name;
+        }
+    }
+
+    private static enum FloatBuilder {
+        SIMPLE {
+            void build(float[] x, int a, int g, int z, int n, int p) {
+                int fromIndex = 0;
+                float negativeValue = -ourRandom.nextFloat();
+                float positiveValue =  ourRandom.nextFloat();
+
+                writeValue(x, negativeValue, fromIndex, n);
+                fromIndex += n;
+
+                writeValue(x, -0.0f, fromIndex, g);
+                fromIndex += g;
+
+                writeValue(x, 0.0f, fromIndex, z);
+                fromIndex += z;
+
+                writeValue(x, positiveValue, fromIndex, p);
+                fromIndex += p;
+
+                writeValue(x, Float.NaN, fromIndex, a);
+            }
+        };
+
+        abstract void build(float[] x, int a, int g, int z, int n, int p);
+    }
+
+    private static enum DoubleBuilder {
+        SIMPLE {
+            void build(double[] x, int a, int g, int z, int n, int p) {
+                int fromIndex = 0;
+                double negativeValue = -ourRandom.nextFloat();
+                double positiveValue =  ourRandom.nextFloat();
+
+                writeValue(x, negativeValue, fromIndex, n);
+                fromIndex += n;
+
+                writeValue(x, -0.0d, fromIndex, g);
+                fromIndex += g;
+
+                writeValue(x, 0.0d, fromIndex, z);
+                fromIndex += z;
+
+                writeValue(x, positiveValue, fromIndex, p);
+                fromIndex += p;
+
+                writeValue(x, Double.NaN, fromIndex, a);
+            }
+        };
+
+        abstract void build(double[] x, int a, int g, int z, int n, int p);
+    }
+
+    private static void writeValue(float[] a, float value, int fromIndex, int count) {
+        for (int i = fromIndex; i < fromIndex + count; i++) {
+            a[i] = value;
+        }
+    }
+
+    private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {
+        for (int i = a.length - numNaN; i < a.length; i++) {
+            if (a[i] == a[i]) {
+                failed("On position " + i + " must be NaN instead of " + a[i]);
+            }
+        }
+        final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
+
+        for (int i = numNeg; i < numNeg + numNegZero; i++) {
+            if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {
+                failed("On position " + i + " must be -0.0 instead of " + a[i]);
+            }
+        }
+        for (int i = 0; i < a.length - numNaN; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void writeValue(double[] a, double value, int fromIndex, int count) {
+        for (int i = fromIndex; i < fromIndex + count; i++) {
+            a[i] = value;
+        }
+    }
+
+    private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {
+        for (int i = a.length - numNaN; i < a.length; i++) {
+            if (a[i] == a[i]) {
+                failed("On position " + i + " must be NaN instead of " + a[i]);
+            }
+        }
+        final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
+
+        for (int i = numNeg; i < numNeg + numNegZero; i++) {
+            if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) {
+                failed("On position " + i + " must be -0.0 instead of " + a[i]);
+            }
+        }
+        for (int i = 0; i < a.length - numNaN; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static enum SortedBuilder {
+        REPEATED {
+            void build(int[] a, int m) {
+                int period = a.length / m;
+                int i = 0;
+                int k = 0;
+
+                while (true) {
+                    for (int t = 1; t <= period; t++) {
+                        if (i >= a.length) {
+                            return;
+                        }
+                        a[i++] = k;
+                    }
+                    if (i >= a.length) {
+                        return;
+                    }
+                    k++;
+                }
+            }
+        },
+
+        ORGAN_PIPES {
+            void build(int[] a, int m) {
+                int i = 0;
+                int k = m;
+
+                while (true) {
+                    for (int t = 1; t <= m; t++) {
+                        if (i >= a.length) {
+                            return;
+                        }
+                        a[i++] = k;
+                    }
+                }
+            }
+        };
+
+        abstract void build(int[] a, int m);
+
+        @Override public String toString() {
+            String name = name();
+
+            for (int i = name.length(); i < 12; i++) {
+                name += " ";
+            }
+            return name;
+        }
+    }
+
+    private static enum UnsortedBuilder {
+        RANDOM {
+            void build(int[] a, int m) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = ourRandom.nextInt();
+                }
+            }
+        },
+        ASCENDING {
+            void build(int[] a, int m) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = m + i;
+                }
+            }
+        },
+        DESCENDING {
+            void build(int[] a, int m) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = a.length - m - i;
+                }
+            }
+        },
+        ALL_EQUAL {
+            void build(int[] a, int m) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = m;
+                }
+            }
+        },
+        SAW {
+            void build(int[] a, int m) {
+                int incCount = 1;
+                int decCount = a.length;
+                int i = 0;
+                int period = m--;
+
+                while (true) {
+                    for (int k = 1; k <= period; k++) {
+                        if (i >= a.length) {
+                            return;
+                        }
+                        a[i++] = incCount++;
+                    }
+                    period += m;
+
+                    for (int k = 1; k <= period; k++) {
+                        if (i >= a.length) {
+                            return;
+                        }
+                        a[i++] = decCount--;
+                    }
+                    period += m;
+                }
+            }
+        },
+        REPEATED {
+            void build(int[] a, int m) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = i % m;
+                }
+            }
+        },
+        DUPLICATED {
+            void build(int[] a, int m) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = ourRandom.nextInt(m);
+                }
+            }
+        },
+        ORGAN_PIPES {
+            void build(int[] a, int m) {
+                int middle = a.length / (m + 1);
+
+                for (int i = 0; i < middle; i++) {
+                    a[i] = i;
+                }
+                for (int i = middle; i < a.length; i++) {
+                    a[i] = a.length - i - 1;
+                }
+            }
+        },
+        STAGGER {
+            void build(int[] a, int m) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = (i * m + i) % a.length;
+                }
+            }
+        },
+        PLATEAU {
+            void build(int[] a, int m) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = Math.min(i, m);
+                }
+            }
+        },
+        SHUFFLE {
+            void build(int[] a, int m) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = ourRandom.nextBoolean() ? (ourFirst += 2) : (ourSecond += 2);
+                }
+            }
+        };
+
+        abstract void build(int[] a, int m);
+
+        @Override public String toString() {
+            String name = name();
+
+            for (int i = name.length(); i < 12; i++) {
+                name += " ";
+            }
+            return name;
+        }
+    }
+
+    private static void checkWithCheckSum(Object test, Object golden) {
+        checkSorted(test);
+        checkCheckSum(test, golden);
+    }
+
+    private static void failed(String message) {
+        err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message);
+        throw new RuntimeException("Test failed - see log file for details");
+    }
+
+    private static void failedSort(int index, String value1, String value2) {
+        failed("Array is not sorted at " + index + "-th position: " +
+            value1 + " and " + value2);
+    }
+
+    private static void failedCompare(int index, String value1, String value2) {
+        failed("On position " + index + " must be " + value2 + " instead of " + value1);
+    }
+
+    private static void compare(Object test, Object golden) {
+        if (test instanceof int[]) {
+            compare((int[]) test, (int[]) golden);
+        } else if (test instanceof long[]) {
+            compare((long[]) test, (long[]) golden);
+        } else if (test instanceof short[]) {
+            compare((short[]) test, (short[]) golden);
+        } else if (test instanceof byte[]) {
+            compare((byte[]) test, (byte[]) golden);
+        } else if (test instanceof char[]) {
+            compare((char[]) test, (char[]) golden);
+        } else if (test instanceof float[]) {
+            compare((float[]) test, (float[]) golden);
+        } else if (test instanceof double[]) {
+            compare((double[]) test, (double[]) golden);
+        } else if (test instanceof Integer[]) {
+            compare((Integer[]) test, (Integer[]) golden);
+        } else {
+            failed("Unknow type of array: " + test + " of class " +
+                test.getClass().getName());
+        }
+    }
+
+    private static void compare(int[] a, int[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(long[] a, long[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(short[] a, short[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(byte[] a, byte[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(char[] a, char[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(float[] a, float[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(double[] a, double[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(Integer[] a, Integer[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i].compareTo(b[i]) != 0) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void checkSorted(Object object) {
+        if (object instanceof int[]) {
+            checkSorted((int[]) object);
+        } else if (object instanceof long[]) {
+            checkSorted((long[]) object);
+        } else if (object instanceof short[]) {
+            checkSorted((short[]) object);
+        } else if (object instanceof byte[]) {
+            checkSorted((byte[]) object);
+        } else if (object instanceof char[]) {
+            checkSorted((char[]) object);
+        } else if (object instanceof float[]) {
+            checkSorted((float[]) object);
+        } else if (object instanceof double[]) {
+            checkSorted((double[]) object);
+        } else if (object instanceof Integer[]) {
+            checkSorted((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void checkSorted(int[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(long[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(short[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(byte[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(char[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(float[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(double[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(Integer[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i].intValue() > a[i + 1].intValue()) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkCheckSum(Object test, Object golden) {
+        if (checkSumXor(test) != checkSumXor(golden)) {
+            failed("Original and sorted arrays are not identical [xor]");
+        }
+        if (checkSumPlus(test) != checkSumPlus(golden)) {
+            failed("Original and sorted arrays are not identical [plus]");
+        }
+    }
+
+    private static int checkSumXor(Object object) {
+        if (object instanceof int[]) {
+            return checkSumXor((int[]) object);
+        } else if (object instanceof long[]) {
+            return checkSumXor((long[]) object);
+        } else if (object instanceof short[]) {
+            return checkSumXor((short[]) object);
+        } else if (object instanceof byte[]) {
+            return checkSumXor((byte[]) object);
+        } else if (object instanceof char[]) {
+            return checkSumXor((char[]) object);
+        } else if (object instanceof float[]) {
+            return checkSumXor((float[]) object);
+        } else if (object instanceof double[]) {
+            return checkSumXor((double[]) object);
+        } else if (object instanceof Integer[]) {
+            return checkSumXor((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+            return -1;
+        }
+    }
+
+    private static int checkSumXor(Integer[] a) {
+        int checkSum = 0;
+
+        for (Integer e : a) {
+            checkSum ^= e.intValue();
+        }
+        return checkSum;
+    }
+
+    private static int checkSumXor(int[] a) {
+        int checkSum = 0;
+
+        for (int e : a) {
+            checkSum ^= e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumXor(long[] a) {
+        long checkSum = 0;
+
+        for (long e : a) {
+            checkSum ^= e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumXor(short[] a) {
+        short checkSum = 0;
+
+        for (short e : a) {
+            checkSum ^= e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumXor(byte[] a) {
+        byte checkSum = 0;
+
+        for (byte e : a) {
+            checkSum ^= e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumXor(char[] a) {
+        char checkSum = 0;
+
+        for (char e : a) {
+            checkSum ^= e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumXor(float[] a) {
+        int checkSum = 0;
+
+        for (float e : a) {
+            checkSum ^= (int) e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumXor(double[] a) {
+        int checkSum = 0;
+
+        for (double e : a) {
+            checkSum ^= (int) e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumPlus(Object object) {
+        if (object instanceof int[]) {
+            return checkSumPlus((int[]) object);
+        } else if (object instanceof long[]) {
+            return checkSumPlus((long[]) object);
+        } else if (object instanceof short[]) {
+            return checkSumPlus((short[]) object);
+        } else if (object instanceof byte[]) {
+            return checkSumPlus((byte[]) object);
+        } else if (object instanceof char[]) {
+            return checkSumPlus((char[]) object);
+        } else if (object instanceof float[]) {
+            return checkSumPlus((float[]) object);
+        } else if (object instanceof double[]) {
+            return checkSumPlus((double[]) object);
+        } else if (object instanceof Integer[]) {
+            return checkSumPlus((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+            return -1;
+        }
+    }
+
+    private static int checkSumPlus(int[] a) {
+        int checkSum = 0;
+
+        for (int e : a) {
+            checkSum += e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumPlus(long[] a) {
+        long checkSum = 0;
+
+        for (long e : a) {
+            checkSum += e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumPlus(short[] a) {
+        short checkSum = 0;
+
+        for (short e : a) {
+            checkSum += e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumPlus(byte[] a) {
+        byte checkSum = 0;
+
+        for (byte e : a) {
+            checkSum += e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumPlus(char[] a) {
+        char checkSum = 0;
+
+        for (char e : a) {
+            checkSum += e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumPlus(float[] a) {
+        int checkSum = 0;
+
+        for (float e : a) {
+            checkSum += (int) e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumPlus(double[] a) {
+        int checkSum = 0;
+
+        for (double e : a) {
+            checkSum += (int) e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumPlus(Integer[] a) {
+        int checkSum = 0;
+
+        for (Integer e : a) {
+            checkSum += e.intValue();
+        }
+        return checkSum;
+    }
+
+    private static void sortByInsertionSort(Object object) {
+        if (object instanceof int[]) {
+            sortByInsertionSort((int[]) object);
+        } else if (object instanceof long[]) {
+            sortByInsertionSort((long[]) object);
+        } else if (object instanceof short[]) {
+            sortByInsertionSort((short[]) object);
+        } else if (object instanceof byte[]) {
+            sortByInsertionSort((byte[]) object);
+        } else if (object instanceof char[]) {
+            sortByInsertionSort((char[]) object);
+        } else if (object instanceof float[]) {
+            sortByInsertionSort((float[]) object);
+        } else if (object instanceof double[]) {
+            sortByInsertionSort((double[]) object);
+        } else if (object instanceof Integer[]) {
+            sortByInsertionSort((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void sortByInsertionSort(int[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            int ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(long[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            long ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(short[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            short ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(byte[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            byte ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(char[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            char ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(float[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            float ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(double[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            double ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(Integer[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            Integer ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sort(Object object) {
+        if (object instanceof int[]) {
+            ForkJoinUtils.parallelSort((int[]) object);
+        } else if (object instanceof long[]) {
+            ForkJoinUtils.parallelSort((long[]) object);
+        } else if (object instanceof short[]) {
+            ForkJoinUtils.parallelSort((short[]) object);
+        } else if (object instanceof byte[]) {
+            ForkJoinUtils.parallelSort((byte[]) object);
+        } else if (object instanceof char[]) {
+            ForkJoinUtils.parallelSort((char[]) object);
+        } else if (object instanceof float[]) {
+            ForkJoinUtils.parallelSort((float[]) object);
+        } else if (object instanceof double[]) {
+            ForkJoinUtils.parallelSort((double[]) object);
+        } else if (object instanceof Integer[]) {
+            ForkJoinUtils.parallelSort((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void sortSubArray(Object object, int fromIndex, int toIndex) {
+        if (object instanceof int[]) {
+            ForkJoinUtils.parallelSort((int[]) object, fromIndex, toIndex);
+        } else if (object instanceof long[]) {
+            ForkJoinUtils.parallelSort((long[]) object, fromIndex, toIndex);
+        } else if (object instanceof short[]) {
+            ForkJoinUtils.parallelSort((short[]) object, fromIndex, toIndex);
+        } else if (object instanceof byte[]) {
+            ForkJoinUtils.parallelSort((byte[]) object, fromIndex, toIndex);
+        } else if (object instanceof char[]) {
+            ForkJoinUtils.parallelSort((char[]) object, fromIndex, toIndex);
+        } else if (object instanceof float[]) {
+            ForkJoinUtils.parallelSort((float[]) object, fromIndex, toIndex);
+        } else if (object instanceof double[]) {
+            ForkJoinUtils.parallelSort((double[]) object, fromIndex, toIndex);
+        } else if (object instanceof Integer[]) {
+            ForkJoinUtils.parallelSort((Integer[]) object, fromIndex, toIndex);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) {
+        if (object instanceof int[]) {
+            checkSubArray((int[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof long[]) {
+            checkSubArray((long[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof short[]) {
+            checkSubArray((short[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof byte[]) {
+            checkSubArray((byte[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof char[]) {
+            checkSubArray((char[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof float[]) {
+            checkSubArray((float[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof double[]) {
+            checkSubArray((double[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof Integer[]) {
+            checkSubArray((Integer[]) object, fromIndex, toIndex, m);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i].intValue() != 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i].intValue() > a[i + 1].intValue()) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i].intValue() != 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (byte) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (byte) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (long) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (long) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (char) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (char) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (short) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (short) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (float) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (float) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (double) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (double) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkRange(Object object, int m) {
+        if (object instanceof int[]) {
+            checkRange((int[]) object, m);
+        } else if (object instanceof long[]) {
+            checkRange((long[]) object, m);
+        } else if (object instanceof short[]) {
+            checkRange((short[]) object, m);
+        } else if (object instanceof byte[]) {
+            checkRange((byte[]) object, m);
+        } else if (object instanceof char[]) {
+            checkRange((char[]) object, m);
+        } else if (object instanceof float[]) {
+            checkRange((float[]) object, m);
+        } else if (object instanceof double[]) {
+            checkRange((double[]) object, m);
+        } else if (object instanceof Integer[]) {
+            checkRange((Integer[]) object, m);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void checkRange(Integer[] a, int m) {
+        try {
+            ForkJoinUtils.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                ForkJoinUtils.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    ForkJoinUtils.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(int[] a, int m) {
+        try {
+            ForkJoinUtils.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                ForkJoinUtils.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    ForkJoinUtils.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(long[] a, int m) {
+        try {
+            ForkJoinUtils.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                ForkJoinUtils.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    ForkJoinUtils.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(byte[] a, int m) {
+        try {
+            ForkJoinUtils.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                ForkJoinUtils.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    ForkJoinUtils.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(short[] a, int m) {
+        try {
+            ForkJoinUtils.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                ForkJoinUtils.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    ForkJoinUtils.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(char[] a, int m) {
+        try {
+            ForkJoinUtils.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                ForkJoinUtils.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    ForkJoinUtils.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(float[] a, int m) {
+        try {
+            ForkJoinUtils.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                ForkJoinUtils.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    ForkJoinUtils.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(double[] a, int m) {
+        try {
+            ForkJoinUtils.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                ForkJoinUtils.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    ForkJoinUtils.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void prepareRandom(int[] a) {
+        for (int i = 0; i < a.length; i++) {
+            a[i] = ourRandom.nextInt();
+        }
+    }
+
+    private static void reset(long seed) {
+        ourRandom = new Random(seed);
+        ourFirst = 0;
+        ourSecond = 0;
+    }
+
+    private static void outArray(Object[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+    }
+
+    private static void outArray(int[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+    }
+
+    private static void outArray(float[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+    }
+
+    private static void outArray(double[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+    }
+
+    private static int ourFirst;
+    private static int ourSecond;
+    private static Random ourRandom;
+    private static String ourDescription;
+}