/*
 * Copyright (c) 2009, 2019, 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.
 */

/*
 * @test
 * @compile/module=java.base java/util/SortingHelper.java
 * @bug 6880672 6896573 6899694 6976036 7013585 7018258 8003981 8226297
 * @build Sorting
 * @run main Sorting -shortrun
 * @summary Exercise Arrays.sort, Arrays.parallelSort
 *
 * @author Vladimir Yaroslavskiy
 * @author Jon Bentley
 * @author Josh Bloch
 */

import java.io.PrintStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
import java.util.SortingHelper;

public class Sorting {

    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, 88, 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, 17000 };

    // Random initial values used in a long run (default)
    private static final long[] LONG_RUN_RANDOMS = { 0xBABA, 0xDEDA, 0xC0FFEE };

    // Random initial values used in a short run
    private static final long[] SHORT_RUN_RANDOMS = { 0xC0FFEE };

    // Constants used in subarray sorting
    private static final int A380 = 0xA380;
    private static final int B747 = 0xB747;

    private static SortingHelper sortingHelper;
    private static String name;

    public static void main(String[] args) {
        boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
        long start = System.currentTimeMillis();

        // Check Dual-Pivot Quicksort
        sortingHelper = SortingHelper.getDualPivotQuicksortHelper();

        if (shortRun) {
            testQuicksort(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
        } else {
            testQuicksort(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
        }

        // Check Parallel sort
        sortingHelper = SortingHelper.getParallelSortHelper();

        if (shortRun) {
            testQuicksort(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
        } else {
            testQuicksort(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
        }

        // Check Heap sort
        sortingHelper = SortingHelper.getHeapSortHelper();
        testHeapSort(shortRun ? SHORT_RUN_RANDOMS : LONG_RUN_RANDOMS);

        // Check Object sort
        if (shortRun) {
            testObject(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
        } else {
            testObject(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
        }

        long end = System.currentTimeMillis();
        out.format("\nPASSED in %d sec.\n", (end - start) / 1000);
    }

    private static void testQuicksort(int[] lengths, long[] randoms) {
        testEmptyAndNullIntArray();
        testEmptyAndNullLongArray();
        testEmptyAndNullByteArray();
        testEmptyAndNullCharArray();
        testEmptyAndNullShortArray();
        testEmptyAndNullFloatArray();
        testEmptyAndNullDoubleArray();

        for (int length : lengths) {
            testMergingSort(length);
            testAndCheckRange(length);
            testAndCheckSubArray(length);
        }

        for (long random : randoms) {
            for (int length : lengths) {
                testAndCheckWithInsertionSort(length, new TestRandom(random));
                testAndCheckWithCheckSum(length, new TestRandom(random));
                testAndCheckWithScrambling(length, new TestRandom(random));
                testFloatNegativeZero(length, new TestRandom(random));
                testAndCheckFloat(length, new TestRandom(random));
                testDoubleNegativeZero(length, new TestRandom(random));
                testAndCheckDouble(length, new TestRandom(random));
            }
        }
    }

    private static void testHeapSort(long[] randoms) {
        for (long random : randoms) {
            for (int length : SHORT_RUN_LENGTHS) {
                testAndCheckWithCheckSum(length, new TestRandom(random));
                testAndCheckWithScrambling(length, new TestRandom(random));
            }
        }
    }

    private static void testObject(int[] lengths, long[] randoms) {
        for (long random : randoms) {
            for (int length : lengths) {
                testObject(length, new TestRandom(random));
                testParallelObject(length, new TestRandom(random));
            }
        }
    }

    private static void testObject(int length, TestRandom random) {
        name = "sorting is stable";
        Pair[] a = build(length, random);
        out.println("[Object Sorting] 'stable'              random = " +
            random.getSeed() + ", length = " + length);
        Arrays.sort(a);
        checkSorted(a);
        checkStable(a);

        a = build(length, random);
        out.println("[Object Sorting] 'comparator'         " +
            " random = " + random.getSeed() + ", length = " + length);
        Arrays.sort(a, pairComparator);
        checkSorted(a);
        checkStable(a);
    }

    private static void testParallelObject(int length, TestRandom random) {
        name = "parallel sorting is stable";
        Pair[] a = build(length, random);
        out.println("[Object Sorting] 'parallel stable'     random = " +
            random.getSeed() + ", length = " + length);
        Arrays.parallelSort(a);
        checkSorted(a);
        checkStable(a);

        a = build(length, random);
        out.println("[Object Sorting] 'parallel comparator'" +
            " random = " + random.getSeed() + ", length = " + length);
        Arrays.parallelSort(a, pairComparator);
        checkSorted(a);
        checkStable(a);
    }

    private static void testEmptyAndNullIntArray() {
        name = "Empty and null array";
        sortingHelper.sort(new int[] {});
        sortingHelper.sort(new int[] {}, 0, 0);

        try {
            sortingHelper.sort((int[]) null);
        } catch (NullPointerException expected) {
            try {
                sortingHelper.sort((int[]) null, 0, 0);
            } catch (NullPointerException expected2) {
                return;
            }
            fail(sortingHelper + "(int[],fromIndex,toIndex) shouldn't " +
                "catch null array");
        }
        fail(sortingHelper + "(int[]) shouldn't catch null array");
    }

    private static void testEmptyAndNullLongArray() {
        name = "Empty and null array";
        sortingHelper.sort(new long[] {});
        sortingHelper.sort(new long[] {}, 0, 0);

        try {
            sortingHelper.sort((long[]) null);
        } catch (NullPointerException expected) {
            try {
                sortingHelper.sort((long[]) null, 0, 0);
            } catch (NullPointerException expected2) {
                return;
            }
            fail(sortingHelper + "(long[],fromIndex,toIndex) shouldn't " +
                "catch null array");
        }
        fail(sortingHelper + "(long[]) shouldn't catch null array");
    }

    private static void testEmptyAndNullByteArray() {
        name = "Empty and null array";
        sortingHelper.sort(new byte[] {});
        sortingHelper.sort(new byte[] {}, 0, 0);

        try {
            sortingHelper.sort((byte[]) null);
        } catch (NullPointerException expected) {
            try {
                sortingHelper.sort((byte[]) null, 0, 0);
            } catch (NullPointerException expected2) {
                return;
            }
            fail(sortingHelper + "(byte[],fromIndex,toIndex) shouldn't " +
                "catch null array");
        }
        fail(sortingHelper + "(byte[]) shouldn't catch null array");
    }

    private static void testEmptyAndNullCharArray() {
        name = "Empty and null array";
        sortingHelper.sort(new char[] {});
        sortingHelper.sort(new char[] {}, 0, 0);

        try {
            sortingHelper.sort((char[]) null);
        } catch (NullPointerException expected) {
            try {
                sortingHelper.sort((char[]) null, 0, 0);
            } catch (NullPointerException expected2) {
                return;
            }
            fail(sortingHelper + "(char[],fromIndex,toIndex) shouldn't " +
                "catch null array");
        }
        fail(sortingHelper + "(char[]) shouldn't catch null array");
    }

    private static void testEmptyAndNullShortArray() {
        name = "Empty and null array";
        sortingHelper.sort(new short[] {});
        sortingHelper.sort(new short[] {}, 0, 0);

        try {
            sortingHelper.sort((short[]) null);
        } catch (NullPointerException expected) {
            try {
                sortingHelper.sort((short[]) null, 0, 0);
            } catch (NullPointerException expected2) {
                return;
            }
            fail(sortingHelper + "(short[],fromIndex,toIndex) shouldn't " +
                "catch null array");
        }
        fail(sortingHelper + "(short[]) shouldn't catch null array");
    }

    private static void testEmptyAndNullFloatArray() {
        name = "Empty and null array";
        sortingHelper.sort(new float[] {});
        sortingHelper.sort(new float[] {}, 0, 0);

        try {
            sortingHelper.sort((float[]) null);
        } catch (NullPointerException expected) {
            try {
                sortingHelper.sort((float[]) null, 0, 0);
            } catch (NullPointerException expected2) {
                return;
            }
            fail(sortingHelper + "(float[],fromIndex,toIndex) shouldn't " +
                "catch null array");
        }
        fail(sortingHelper + "(float[]) shouldn't catch null array");
    }

    private static void testEmptyAndNullDoubleArray() {
        name = "Empty and null array";
        sortingHelper.sort(new double[] {});
        sortingHelper.sort(new double[] {}, 0, 0);

        try {
            sortingHelper.sort((double[]) null);
        } catch (NullPointerException expected) {
            try {
                sortingHelper.sort((double[]) null, 0, 0);
            } catch (NullPointerException expected2) {
                return;
            }
            fail(sortingHelper + "(double[],fromIndex,toIndex) shouldn't " +
                "catch null array");
        }
        fail(sortingHelper + "(double[]) shouldn't catch null array");
    }

    private static void testAndCheckSubArray(int length) {
        name = "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);
            int[] test = golden.clone();

            for (TypeConverter converter : TypeConverter.values()) {
                out.println(getTestName() + converter +
                    " length = " + length + ", m = " + m);
                Object convertedTest = converter.convert(test);
                sortSubArray(convertedTest, fromIndex, toIndex);
                checkSubArray(convertedTest, fromIndex, toIndex);
            }
        }
        if (newLine) {
            out.println();
        }
    }

    private static void testAndCheckRange(int length) {
        name = "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(getTestName() + converter +
                    " length = " + length + ", m = " + m);
                Object convertedGolden = converter.convert(golden);
                checkRange(convertedGolden, m);
            }
        }
        out.println();
    }

    private static void checkSorted(Pair[] a) {
        for (int i = 0; i < a.length - 1; ++i) {
            if (a[i].getKey() > a[i + 1].getKey()) {
                failSort(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)) {
                fail("On position " + i + " keys are different " +
                    key1 + ", " + key2 + ", " + key3 + ", " + key4);
            }
            if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
                fail("Sorting is not stable at position " + i +
                    ". Second values have been changed: " + value1 + ", " +
                    value2 + ", " + value3 + ", " + value4);
            }
        }
    }

    private static Pair[] build(int length, Random random) {
        Pair[] a = new Pair[length * 4];

        for (int i = 0; i < a.length; ) {
            int key = random.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 Comparator<Pair> pairComparator = new Comparator<Pair>() {

        @Override
        public int compare(Pair p1, Pair p2) {
            return p1.compareTo(p2);
        }
    };

    private static class Pair implements Comparable<Pair> {

        private Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }

        int getKey() {
            return key;
        }

        int getValue() {
            return value;
        }

        @Override
        public int compareTo(Pair pair) {
            return Integer.compare(key, pair.key);
        }

        @Override
        public String toString() {
            return "(" + key + ", " + value + ")";
        }

        private int key;
        private int value;
    }

    private static void testAndCheckWithInsertionSort(int length, TestRandom random) {
        if (length > 1000) {
            return;
        }
        name = "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, random);
                int[] test = golden.clone();

                for (TypeConverter converter : TypeConverter.values()) {
                    out.println(getTestName() + converter + " " +
                        builder + "random = " + random.getSeed() + ", length = " +
                        length + ", m = " + m);
                    Object convertedTest1 = converter.convert(test);
                    Object convertedTest2 = converter.convert(test);
                    sort(convertedTest1);
                    sortByInsertionSort(convertedTest2);
                    compare(convertedTest1, convertedTest2);
                }
            }
        }
        out.println();
    }

    private static void testMergingSort(int length) {
        if (length < 1000) {
            return;
        }
        name = "Merging sort";
        int[] golden = new int[length];
        final int PERIOD = 50;

        for (int m = PERIOD - 2; m <= PERIOD + 2; ++m) {
            for (MergingBuilder builder : MergingBuilder.values()) {
                builder.build(golden, m);

                for (TypeConverter converter : TypeConverter.values()) {
                    out.println(getTestName() + converter +
                        " " + builder + "length = " + length + ", m = " + m);
                    Object convertedGolden = converter.convert(golden);
                    sort(convertedGolden);
                    checkSorted(convertedGolden);
                }
            }
        }
        out.println();
    }

    private static void testAndCheckWithCheckSum(int length, TestRandom random) {
        name = "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, random);
                int[] test = golden.clone();

                for (TypeConverter converter : TypeConverter.values()) {
                    out.println(getTestName() + converter +
                        " " + builder + "random = " + random.getSeed() +
                        ", 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, TestRandom random) {
        name = "Sorting with scrambling";
        int[] golden = new int[length];

        for (int m = 1; m < 8; ++m) {
            if (m > length) {
                break;
            }
            for (SortedBuilder builder : SortedBuilder.values()) {
                builder.build(golden, m);
                int[] test = golden.clone();
                scramble(test, random);

                for (TypeConverter converter : TypeConverter.values()) {
                    out.println(getTestName() + converter +
                        " " + builder + "random = " + random.getSeed() +
                        ", 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, TestRandom random) {
        name = "Float sorting";
        float[] golden = new float[length];
        boolean newLine = false;
        final int MAX = 13;

        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;
                            }
                            for (FloatBuilder builder : FloatBuilder.values()) {
                                out.println(getTestName() + "random = " +
                                    random.getSeed() + " length = " + length +
                                    ", a = " + a + ", g = " + g + ", z = " + z +
                                    ", n = " + n + ", p = " + p);
                                builder.build(golden, a, g, z, n, p, random);
                                float[] test = golden.clone();
                                scramble(test, random);
                                sort(test);
                                compare(test, golden, a, n, g);
                            }
                            newLine = true;
                        }
                    }
                }
            }
        }
        if (newLine) {
            out.println();
        }

        for (int m = 13; m > 4; --m) {
            int t = length / m;
            int g = t, z = t, n = t, p = t;
            int a = length - g - z - n - p;

            for (FloatBuilder builder : FloatBuilder.values()) {
                out.println(getTestName() + "random = " +
                    random.getSeed() + " length = " + length +
                    ", a = " + a + ", g = " + g + ", z = " + z +
                    ", n = " + n + ", p = " + p);
                builder.build(golden, a, g, z, n, p, random);
                float[] test = golden.clone();
                scramble(test, random);
                sort(test);
                compare(test, golden, a, n, g);
            }
        }
        out.println();
    }

    private static void testFloatNegativeZero(int length, TestRandom random) {
        name = "Float -0.0";
        out.println(getTestName() + "random = " + random.getSeed() + " length = " + length);
        float[] a = new float[length];

        for (int i = 0; i < length; ++i) {
            a[i] = random.nextBoolean() ? -0.0f : 0.0f;
        }
        sort(a);
        checkNegativeZero(a);
        out.println();
    }

    private static void testAndCheckDouble(int length, TestRandom random) {
        name = "Double sorting";
        double[] golden = new double[length];
        boolean newLine = false;
        final int MAX = 13;

        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;
                            }
                            for (DoubleBuilder builder : DoubleBuilder.values()) {
                                out.println(getTestName() + "random = " +
                                    random.getSeed() + " length = " + length +
                                    ", a = " + a + ", g = " + g + ", z = " + z +
                                    ", n = " + n + ", p = " + p);
                                builder.build(golden, a, g, z, n, p, random);
                                double[] test = golden.clone();
                                scramble(test, random);
                                sort(test);
                                compare(test, golden, a, n, g);
                            }
                            newLine = true;
                        }
                    }
                }
            }
        }
        if (newLine) {
            out.println();
        }

        for (int m = 13; m > 4; --m) {
            int t = length / m;
            int g = t, z = t, n = t, p = t;
            int a = length - g - z - n - p;

            for (DoubleBuilder builder : DoubleBuilder.values()) {
                out.println(getTestName() + "random = " +
                    random.getSeed() + " length = " + length +
                    ", a = " + a + ", g = " + g + ", z = " + z +
                    ", n = " + n + ", p = " + p);
                builder.build(golden, a, g, z, n, p, random);
                double[] test = golden.clone();
                scramble(test, random);
                sort(test);
                compare(test, golden, a, n, g);
            }
        }
        out.println();
    }

    private static void testDoubleNegativeZero(int length, TestRandom random) {
        name = "Double -0.0";
        out.println(getTestName() + "random = " + random.getSeed() + " length = " + length);
        double[] a = new double[length];

        for (int i = 0; i < length; ++i) {
            a[i] = random.nextBoolean() ? -0.0d : 0.0d;
        }
        sort(a);
        checkNegativeZero(a);
        out.println();
    }

    private static void prepareSubArray(int[] a, int fromIndex, int toIndex) {
        for (int i = 0; i < fromIndex; ++i) {
            a[i] = A380;
        }
        int middle = (fromIndex + toIndex) >>> 1;
        int k = 0;

        for (int i = fromIndex; i < middle; ++i) {
            a[i] = k++;
        }
        for (int i = middle; i < toIndex; ++i) {
            a[i] = k--;
        }
        for (int i = toIndex; i < a.length; ++i) {
            a[i] = B747;
        }
    }

    private static void scramble(int[] a, Random random) {
        for (int i = 0; i < a.length * 7; ++i) {
            swap(a, random.nextInt(a.length), random.nextInt(a.length));
        }
    }

    private static void scramble(float[] a, Random random) {
        for (int i = 0; i < a.length * 7; ++i) {
            swap(a, random.nextInt(a.length), random.nextInt(a.length));
        }
    }

    private static void scramble(double[] a, Random random) {
        for (int i = 0; i < a.length * 7; ++i) {
            swap(a, random.nextInt(a.length), random.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 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;
            }
        };

        abstract Object convert(int[] a);

        @Override
        public String toString() {
            String name = name();

            for (int i = name.length(); i < 9; ++i) {
                name += " ";
            }
            return name;
        }
    }

    private enum FloatBuilder {

        SIMPLE {
            void build(float[] x, int a, int g, int z, int n, int p, Random random) {
                int fromIndex = 0;
                float negativeValue = -random.nextFloat();
                float positiveValue =  random.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, Random random);
    }

    private enum DoubleBuilder {

        SIMPLE {
            void build(double[] x, int a, int g, int z, int n, int p, Random random) {
                int fromIndex = 0;
                double negativeValue = -random.nextFloat();
                double positiveValue =  random.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, Random random);
    }

    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]) {
                fail("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])) {
                fail("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]) {
                failCompare(i, "" + a[i], "" + b[i]);
            }
        }
    }

    private static void checkNegativeZero(float[] a) {
        for (int i = 0; i < a.length - 1; ++i) {
            if (Float.floatToRawIntBits(a[i]) == 0 && Float.floatToRawIntBits(a[i + 1]) < 0) {
                fail(a[i] + " goes before " + a[i + 1] + " at " + 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]) {
                fail("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])) {
                fail("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]) {
                failCompare(i, "" + a[i], "" + b[i]);
            }
        }
    }

    private static void checkNegativeZero(double[] a) {
        for (int i = 0; i < a.length - 1; ++i) {
            if (Double.doubleToRawLongBits(a[i]) == 0 && Double.doubleToRawLongBits(a[i + 1]) < 0) {
                fail(a[i] + " goes before " + a[i + 1] + " at " + i);
            }
        }
    }

    private enum SortedBuilder {

        STEPS {
            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;
                }
            }
        };

        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 enum UnsortedBuilder {

        RANDOM {
            void build(int[] a, int m, Random random) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = random.nextInt();
                }
            }
        },

        ASCENDING {
            void build(int[] a, int m, Random random) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = m + i;
                }
            }
        },

        DESCENDING {
            void build(int[] a, int m, Random random) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = a.length - m - i;
                }
            }
        },

        EQUAL {
            void build(int[] a, int m, Random random) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = m;
                }
            }
        },

        SAW {
            void build(int[] a, int m, Random random) {
                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, Random random) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = i % m;
                }
            }
        },

        DUPLICATED {
            void build(int[] a, int m, Random random) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = random.nextInt(m);
                }
            }
        },

        ORGAN_PIPES {
            void build(int[] a, int m, Random random) {
                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, Random random) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = (i * m + i) % a.length;
                }
            }
        },

        PLATEAU {
            void build(int[] a, int m, Random random) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = Math.min(i, m);
                }
            }
        },

        SHUFFLE {
            void build(int[] a, int m, Random random) {
                int x = 0, y = 0;
                for (int i = 0; i < a.length; ++i) {
                    a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
                }
            }
        },

        LATCH {
            void build(int[] a, int m, Random random) {
                int max = a.length / m;
                max = max < 2 ? 2 : max;

                for (int i = 0; i < a.length; ++i) {
                    a[i] = i % max;
                }
            }
        };

        abstract void build(int[] a, int m, Random random);

        @Override
        public String toString() {
            String name = name();

            for (int i = name.length(); i < 12; ++i) {
                name += " ";
            }
            return name;
        }
    }

    private enum MergingBuilder {

        ASCENDING {
            void build(int[] a, int m) {
                int period = a.length / m;
                int v = 1, i = 0;

                for (int k = 0; k < m; ++k) {
                    v = 1;
                    for (int p = 0; p < period; ++p) {
                        a[i++] = v++;
                    }
                }
                for (int j = i; j < a.length - 1; ++j) {
                    a[j] = v++;
                }
                a[a.length - 1] = 0;
            }
        },

        DESCENDING {
            void build(int[] a, int m) {
                int period = a.length / m;
                int v = -1, i = 0;

                for (int k = 0; k < m; ++k) {
                    v = -1;
                    for (int p = 0; p < period; ++p) {
                        a[i++] = v--;
                    }
                }
                for (int j = i; j < a.length - 1; ++j) {
                    a[j] = v--;
                }
                a[a.length - 1] = 0;
            }
        },

        POINT {
            void build(int[] a, int m) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = 0;
                }
                a[a.length / 2] = m;
            }
        },

        LINE {
            void build(int[] a, int m) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = i;
                }
                reverse(a, 0, a.length - 1);
            }
        },

        PEARL {
            void build(int[] a, int m) {
                for (int i = 0; i < a.length; ++i) {
                    a[i] = i;
                }
                reverse(a, 0, 2);
            }
        },

        RING {
            void build(int[] a, int m) {
                int k1 = a.length / 3;
                int k2 = a.length / 3 * 2;
                int level = a.length / 3;

                for (int i = 0, k = level; i < k1; ++i) {
                    a[i] = k--;
                }
                for (int i = k1; i < k2; ++i) {
                    a[i] = 0;
                }
                for (int i = k2, k = level; i < a.length; ++i) {
                    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 void reverse(int[] a, int lo, int hi) {
        for (--hi; lo < hi; ) {
            int tmp = a[lo];
            a[lo++] = a[hi];
            a[hi--] = tmp;
        }
    }

    private static void checkWithCheckSum(Object test, Object golden) {
        checkSorted(test);
        checkCheckSum(test, golden);
    }

    private static void fail(String message) {
        err.format("\n*** TEST FAILED *** %s.\n\n%s.\n\n", name, message);
        throw new RuntimeException("Test failed - see log file for details");
    }

    private static void failSort(int index, String value1, String value2) {
        fail("Array is not sorted at " + index + "-th position: " + value1 + " and " + value2);
    }

    private static void failCompare(int index, String value1, String value2) {
        fail("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 {
            fail("Unknown 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]) {
                failCompare(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]) {
                failCompare(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]) {
                failCompare(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]) {
                failCompare(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]) {
                failCompare(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]) {
                failCompare(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]) {
                failCompare(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 {
            fail("Unknown 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]) {
                failSort(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]) {
                failSort(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]) {
                failSort(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]) {
                failSort(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]) {
                failSort(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]) {
                failSort(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]) {
                failSort(i, "" + a[i], "" + a[i + 1]);
            }
        }
    }

    private static void checkCheckSum(Object test, Object golden) {
        if (checkSumXor(test) != checkSumXor(golden)) {
            fail("Original and sorted arrays are not identical [xor]");
        }
        if (checkSumPlus(test) != checkSumPlus(golden)) {
            fail("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 {
            fail("Unknown type of array: " + object + " of class " +
                object.getClass().getName());
            return -1;
        }
    }

    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 {
            fail("Unknown 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 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 {
            fail("Unknown 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 sort(Object object) {
        if (object instanceof int[]) {
            sortingHelper.sort((int[]) object);
        } else if (object instanceof long[]) {
            sortingHelper.sort((long[]) object);
        } else if (object instanceof short[]) {
            sortingHelper.sort((short[]) object);
        } else if (object instanceof byte[]) {
            sortingHelper.sort((byte[]) object);
        } else if (object instanceof char[]) {
            sortingHelper.sort((char[]) object);
        } else if (object instanceof float[]) {
            sortingHelper.sort((float[]) object);
        } else if (object instanceof double[]) {
            sortingHelper.sort((double[]) object);
        } else {
            fail("Unknown type of array: " + object + " of class " +
                object.getClass().getName());
        }
    }

    private static void sortSubArray(Object object, int fromIndex, int toIndex) {
        if (object instanceof int[]) {
            sortingHelper.sort((int[]) object, fromIndex, toIndex);
        } else if (object instanceof long[]) {
            sortingHelper.sort((long[]) object, fromIndex, toIndex);
        } else if (object instanceof short[]) {
            sortingHelper.sort((short[]) object, fromIndex, toIndex);
        } else if (object instanceof byte[]) {
            sortingHelper.sort((byte[]) object, fromIndex, toIndex);
        } else if (object instanceof char[]) {
            sortingHelper.sort((char[]) object, fromIndex, toIndex);
        } else if (object instanceof float[]) {
            sortingHelper.sort((float[]) object, fromIndex, toIndex);
        } else if (object instanceof double[]) {
            sortingHelper.sort((double[]) object, fromIndex, toIndex);
        } else {
            fail("Unknown type of array: " + object + " of class " +
                object.getClass().getName());
        }
    }

    private static void checkSubArray(Object object, int fromIndex, int toIndex) {
        if (object instanceof int[]) {
            checkSubArray((int[]) object, fromIndex, toIndex);
        } else if (object instanceof long[]) {
            checkSubArray((long[]) object, fromIndex, toIndex);
        } else if (object instanceof short[]) {
            checkSubArray((short[]) object, fromIndex, toIndex);
        } else if (object instanceof byte[]) {
            checkSubArray((byte[]) object, fromIndex, toIndex);
        } else if (object instanceof char[]) {
            checkSubArray((char[]) object, fromIndex, toIndex);
        } else if (object instanceof float[]) {
            checkSubArray((float[]) object, fromIndex, toIndex);
        } else if (object instanceof double[]) {
            checkSubArray((double[]) object, fromIndex, toIndex);
        } else {
            fail("Unknown type of array: " + object + " of class " +
                object.getClass().getName());
        }
    }

    private static void checkSubArray(int[] a, int fromIndex, int toIndex) {
        for (int i = 0; i < fromIndex; ++i) {
            if (a[i] != A380) {
                fail("Range sort changes left element on position " + i +
                    ": " + a[i] + ", must be " + A380);
            }
        }

        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (a[i] > a[i + 1]) {
                failSort(i, "" + a[i], "" + a[i + 1]);
            }
        }

        for (int i = toIndex; i < a.length; ++i) {
            if (a[i] != B747) {
                fail("Range sort changes right element on position " + i +
                    ": " + a[i] + ", must be " + B747);
            }
        }
    }

    private static void checkSubArray(byte[] a, int fromIndex, int toIndex) {
        for (int i = 0; i < fromIndex; ++i) {
            if (a[i] != (byte) A380) {
                fail("Range sort changes left element on position " + i +
                    ": " + a[i] + ", must be " + A380);
            }
        }

        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (a[i] > a[i + 1]) {
                failSort(i, "" + a[i], "" + a[i + 1]);
            }
        }

        for (int i = toIndex; i < a.length; ++i) {
            if (a[i] != (byte) B747) {
                fail("Range sort changes right element on position " + i +
                    ": " + a[i] + ", must be " + B747);
            }
        }
    }

    private static void checkSubArray(long[] a, int fromIndex, int toIndex) {
        for (int i = 0; i < fromIndex; ++i) {
            if (a[i] != (long) A380) {
                fail("Range sort changes left element on position " + i +
                    ": " + a[i] + ", must be " + A380);
            }
        }

        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (a[i] > a[i + 1]) {
                failSort(i, "" + a[i], "" + a[i + 1]);
            }
        }

        for (int i = toIndex; i < a.length; ++i) {
            if (a[i] != (long) B747) {
                fail("Range sort changes right element on position " + i +
                    ": " + a[i] + ", must be " + B747);
            }
        }
    }

    private static void checkSubArray(char[] a, int fromIndex, int toIndex) {
        for (int i = 0; i < fromIndex; ++i) {
            if (a[i] != (char) A380) {
                fail("Range sort changes left element on position " + i +
                    ": " + a[i] + ", must be " + A380);
            }
        }

        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (a[i] > a[i + 1]) {
                failSort(i, "" + a[i], "" + a[i + 1]);
            }
        }

        for (int i = toIndex; i < a.length; ++i) {
            if (a[i] != (char) B747) {
                fail("Range sort changes right element on position " + i +
                    ": " + a[i] + ", must be " + B747);
            }
        }
    }

    private static void checkSubArray(short[] a, int fromIndex, int toIndex) {
        for (int i = 0; i < fromIndex; ++i) {
            if (a[i] != (short) A380) {
                fail("Range sort changes left element on position " + i +
                    ": " + a[i] + ", must be " + A380);
            }
        }

        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (a[i] > a[i + 1]) {
                failSort(i, "" + a[i], "" + a[i + 1]);
            }
        }

        for (int i = toIndex; i < a.length; ++i) {
            if (a[i] != (short) B747) {
                fail("Range sort changes right element on position " + i +
                    ": " + a[i] + ", must be " + B747);
            }
        }
    }

    private static void checkSubArray(float[] a, int fromIndex, int toIndex) {
        for (int i = 0; i < fromIndex; ++i) {
            if (a[i] != (float) A380) {
                fail("Range sort changes left element on position " + i +
                    ": " + a[i] + ", must be " + A380);
            }
        }

        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (a[i] > a[i + 1]) {
                failSort(i, "" + a[i], "" + a[i + 1]);
            }
        }

        for (int i = toIndex; i < a.length; ++i) {
            if (a[i] != (float) B747) {
                fail("Range sort changes right element on position " + i +
                    ": " + a[i] + ", must be " + B747);
            }
        }
    }

    private static void checkSubArray(double[] a, int fromIndex, int toIndex) {
        for (int i = 0; i < fromIndex; ++i) {
            if (a[i] != (double) A380) {
                fail("Range sort changes left element on position " + i +
                    ": " + a[i] + ", must be " + A380);
            }
        }

        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (a[i] > a[i + 1]) {
                failSort(i, "" + a[i], "" + a[i + 1]);
            }
        }

        for (int i = toIndex; i < a.length; ++i) {
            if (a[i] != (double) B747) {
                fail("Range sort changes right element on position " + i +
                    ": " + a[i] + ", must be " + B747);
            }
        }
    }

    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 {
            fail("Unknown type of array: " + object + " of class " +
                object.getClass().getName());
        }
    }

    private static void checkRange(int[] a, int m) {
        try {
            sortingHelper.sort(a, m + 1, m);

            fail(sortingHelper + "() does not throw IllegalArgumentException " +
                " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
        } catch (IllegalArgumentException iae) {
            try {
                sortingHelper.sort(a, -m, a.length);

                fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                    " as expected: fromIndex = " + (-m));
            } catch (ArrayIndexOutOfBoundsException aoe) {
                try {
                    sortingHelper.sort(a, 0, a.length + m);

                    fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                        " as expected: toIndex = " + (a.length + m));
                } catch (ArrayIndexOutOfBoundsException expected) {
                }
            }
        }
    }

    private static void checkRange(long[] a, int m) {
        try {
            sortingHelper.sort(a, m + 1, m);

            fail(sortingHelper + "() does not throw IllegalArgumentException " +
                " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
        } catch (IllegalArgumentException iae) {
            try {
                sortingHelper.sort(a, -m, a.length);

                fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                    " as expected: fromIndex = " + (-m));
            } catch (ArrayIndexOutOfBoundsException aoe) {
                try {
                    sortingHelper.sort(a, 0, a.length + m);

                    fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                        " as expected: toIndex = " + (a.length + m));
                } catch (ArrayIndexOutOfBoundsException expected) {
                }
            }
        }
    }

    private static void checkRange(byte[] a, int m) {
        try {
            sortingHelper.sort(a, m + 1, m);

            fail(sortingHelper + "() does not throw IllegalArgumentException " +
                " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
        } catch (IllegalArgumentException iae) {
            try {
                sortingHelper.sort(a, -m, a.length);

                fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                    " as expected: fromIndex = " + (-m));
            } catch (ArrayIndexOutOfBoundsException aoe) {
                try {
                    sortingHelper.sort(a, 0, a.length + m);

                    fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                        " as expected: toIndex = " + (a.length + m));
                } catch (ArrayIndexOutOfBoundsException expected) {
                }
            }
        }
    }

    private static void checkRange(short[] a, int m) {
        try {
            sortingHelper.sort(a, m + 1, m);

            fail(sortingHelper + "() does not throw IllegalArgumentException " +
                " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
        } catch (IllegalArgumentException iae) {
            try {
                sortingHelper.sort(a, -m, a.length);

                fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                    " as expected: fromIndex = " + (-m));
            } catch (ArrayIndexOutOfBoundsException aoe) {
                try {
                    sortingHelper.sort(a, 0, a.length + m);

                    fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                        " as expected: toIndex = " + (a.length + m));
                } catch (ArrayIndexOutOfBoundsException expected) {
                }
            }
        }
    }

    private static void checkRange(char[] a, int m) {
        try {
            sortingHelper.sort(a, m + 1, m);

            fail(sortingHelper + "() does not throw IllegalArgumentException " +
                " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
        } catch (IllegalArgumentException iae) {
            try {
                sortingHelper.sort(a, -m, a.length);

                fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                    " as expected: fromIndex = " + (-m));
            } catch (ArrayIndexOutOfBoundsException aoe) {
                try {
                    sortingHelper.sort(a, 0, a.length + m);

                    fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                        " as expected: toIndex = " + (a.length + m));
                } catch (ArrayIndexOutOfBoundsException expected) {
                }
            }
        }
    }

    private static void checkRange(float[] a, int m) {
        try {
            sortingHelper.sort(a, m + 1, m);

            fail(sortingHelper + "() does not throw IllegalArgumentException " +
                " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
        } catch (IllegalArgumentException iae) {
            try {
                sortingHelper.sort(a, -m, a.length);

                fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                    " as expected: fromIndex = " + (-m));
            } catch (ArrayIndexOutOfBoundsException aoe) {
                try {
                    sortingHelper.sort(a, 0, a.length + m);

                    fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                        " as expected: toIndex = " + (a.length + m));
                } catch (ArrayIndexOutOfBoundsException expected) {
                }
            }
        }
    }

    private static void checkRange(double[] a, int m) {
        try {
            sortingHelper.sort(a, m + 1, m);

            fail(sortingHelper + "() does not throw IllegalArgumentException " +
                " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
        } catch (IllegalArgumentException iae) {
            try {
                sortingHelper.sort(a, -m, a.length);

                fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                    " as expected: fromIndex = " + (-m));
            } catch (ArrayIndexOutOfBoundsException aoe) {
                try {
                    sortingHelper.sort(a, 0, a.length + m);

                    fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
                        " as expected: toIndex = " + (a.length + m));
                } catch (ArrayIndexOutOfBoundsException expected) {
                }
            }
        }
    }

    private static String getTestName() {
        return "[" + sortingHelper + "] '" + name + "' ";
    }

    private static class TestRandom extends Random {

        private TestRandom(long seed) {
            super(seed);
            this.seed = Long.toHexString(seed).toUpperCase();
        }

        String getSeed() {
            return seed;
        }

        private String seed;
    }
}