1 /*
   2  * Copyright (c) 2009, 2023, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test

  26  * @bug 6880672 6896573 6899694 6976036 7013585 7018258 8003981 8226297
  27  * @library /test/lib
  28  * @compile/module=java.base java/util/SortingHelper.java
  29  * @build Sorting
  30  * @run main/othervm -XX:+UnlockDiagnosticVMOptions -XX:DisableIntrinsic=_arraySort,_arrayPartition Sorting -shortrun
  31  * @run main/othervm -XX:-TieredCompilation -XX:CompileCommand=CompileThresholdScaling,java.util.DualPivotQuicksort::sort,0.0001 Sorting -shortrun
  32  * @summary Exercise Arrays.sort, Arrays.parallelSort
  33  *
  34  * @author Vladimir Yaroslavskiy
  35  * @author Jon Bentley
  36  * @author Josh Bloch
  37  */
  38 
  39 import java.io.PrintStream;
  40 import java.util.Comparator;
  41 import java.util.Random;
  42 import java.util.SortingHelper;
  43 
  44 import jdk.test.lib.valueclass.AsValueClass;
  45 
  46 public class Sorting {
  47 
  48     private static final PrintStream out = System.out;
  49     private static final PrintStream err = System.err;
  50 
  51     // Array lengths used in a long run (default)
  52     private static final int[] LONG_RUN_LENGTHS = {
  53         1, 3, 8, 21, 55, 100, 1_000, 10_000, 100_000 };
  54 
  55     // Array lengths used in a short run
  56     private static final int[] SHORT_RUN_LENGTHS = {
  57         1, 8, 55, 100, 10_000 };
  58 
  59     // Random initial values used in a long run (default)
  60     private static final TestRandom[] LONG_RUN_RANDOMS = {
  61         TestRandom.BABA, TestRandom.DEDA, TestRandom.C0FFEE };
  62 
  63     // Random initial values used in a short run
  64     private static final TestRandom[] SHORT_RUN_RANDOMS = {
  65         TestRandom.C0FFEE };
  66 
  67     // Constants used in subarray sorting
  68     private static final int A380 = 0xA380;
  69     private static final int B747 = 0xB747;
  70 
  71     private final SortingHelper sortingHelper;
  72     private final TestRandom[] randoms;
  73     private final int[] lengths;
  74     private Object[] gold;
  75     private Object[] test;
  76 
  77     @AsValueClass
  78     record Point(int x, int y) implements Comparable<Point> {
  79         public int compareTo(Point p) {
  80             return Integer.compare(x * x + y * y, p.x * p.x + p.y * p.y);
  81         }
  82     }
  83 
  84     public static void main(String[] args) {
  85         long start = System.currentTimeMillis();
  86         boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
  87 
  88         int[] lengths = shortRun ? SHORT_RUN_LENGTHS : LONG_RUN_LENGTHS;
  89         TestRandom[] randoms = shortRun ? SHORT_RUN_RANDOMS : LONG_RUN_RANDOMS;
  90 
  91         new Sorting(SortingHelper.DUAL_PIVOT_QUICKSORT, randoms, lengths).testCore();
  92         new Sorting(SortingHelper.PARALLEL_SORT, randoms, lengths).testCore();
  93         new Sorting(SortingHelper.HEAP_SORT, randoms, lengths).testBasic();
  94         new Sorting(SortingHelper.ARRAYS_SORT, randoms, lengths).testAll();
  95         new Sorting(SortingHelper.ARRAYS_PARALLEL_SORT, randoms, lengths).testAll();
  96 
  97         long end = System.currentTimeMillis();
  98         out.format("PASSED in %d sec.\n", (end - start) / 1000);
  99     }
 100 
 101     private Sorting(SortingHelper sortingHelper, TestRandom[] randoms, int[] lengths) {
 102         this.sortingHelper = sortingHelper;
 103         this.randoms = randoms;
 104         this.lengths = lengths;
 105     }
 106 
 107     private void testBasic() {
 108         testEmptyArray();
 109 
 110         for (int length : lengths) {
 111             createData(length);
 112             testBasic(length);
 113         }
 114     }
 115 
 116     private void testBasic(int length) {
 117         for (TestRandom random : randoms) {
 118             testWithInsertionSort(length, random);
 119             testWithCheckSum(length, random);
 120             testWithScrambling(length, random);
 121         }
 122     }
 123 
 124     private void testCore() {
 125         for (int length : lengths) {
 126             createData(length);
 127             testCore(length);
 128         }
 129     }
 130 
 131     private void testCore(int length) {
 132         testBasic(length);
 133 
 134         for (TestRandom random : randoms) {
 135             testMergingSort(length, random);
 136             testSubArray(length, random);
 137             testNegativeZero(length, random);
 138             testFloatingPointSorting(length, random);
 139         }
 140     }
 141 
 142     private void testAll() {
 143         for (int length : lengths) {
 144             createData(length);
 145             testAll(length);
 146         }
 147     }
 148 
 149     private void testAll(int length) {
 150         testCore(length);
 151 
 152         for (TestRandom random : randoms) {
 153             testRange(length, random);
 154             testStability(length, random);
 155             testValueClass(length, random);
 156         }
 157     }
 158 
 159     private void testValueClass(int length, TestRandom random) {
 160         printTestName("Test value class (Point[])", random, length);
 161 
 162         Point[] points = new Point[length];
 163         for (int i = 0; i < length; i++) {
 164             points[i] = new Point(random.nextInt(10) - 5, random.nextInt(10) - 5);
 165         }
 166 
 167         sortingHelper.sort(points);
 168         checkSorted(points);
 169 
 170         Comparator<Point> byXThenY = Comparator.comparingInt(Point::x).thenComparingInt(Point::y);
 171         sortingHelper.sort(points, byXThenY);
 172         checkSorted(points, byXThenY);
 173 
 174         out.println();
 175     }
 176 
 177     private void testEmptyArray() {
 178         testEmptyAndNullIntArray();
 179         testEmptyAndNullLongArray();
 180         testEmptyAndNullByteArray();
 181         testEmptyAndNullCharArray();
 182         testEmptyAndNullShortArray();
 183         testEmptyAndNullFloatArray();
 184         testEmptyAndNullDoubleArray();
 185     }
 186 
 187     private void testStability(int length, TestRandom random) {
 188         printTestName("Test stability", random, length);
 189 
 190         Pair[] a = build(length, random);
 191         sortingHelper.sort(a);
 192         checkSorted(a);
 193         checkStable(a);
 194 
 195         a = build(length, random);
 196         sortingHelper.sort(a, pairComparator);
 197         checkSorted(a);
 198         checkStable(a);
 199 
 200         out.println();
 201     }
 202 
 203     private void testEmptyAndNullIntArray() {
 204         sortingHelper.sort(new int[] {});
 205         sortingHelper.sort(new int[] {}, 0, 0);
 206 
 207         try {
 208             sortingHelper.sort(null);
 209         } catch (NullPointerException expected) {
 210             try {
 211                 sortingHelper.sort(null, 0, 0);
 212             } catch (NullPointerException expected2) {
 213                 return;
 214             }
 215             fail(sortingHelper + "(int[],fromIndex,toIndex) shouldn't " +
 216                 "catch null array");
 217         }
 218         fail(sortingHelper + "(int[]) shouldn't catch null array");
 219     }
 220 
 221     private void testEmptyAndNullLongArray() {
 222         sortingHelper.sort(new long[] {});
 223         sortingHelper.sort(new long[] {}, 0, 0);
 224 
 225         try {
 226             sortingHelper.sort(null);
 227         } catch (NullPointerException expected) {
 228             try {
 229                 sortingHelper.sort(null, 0, 0);
 230             } catch (NullPointerException expected2) {
 231                 return;
 232             }
 233             fail(sortingHelper + "(long[],fromIndex,toIndex) shouldn't " +
 234                 "catch null array");
 235         }
 236         fail(sortingHelper + "(long[]) shouldn't catch null array");
 237     }
 238 
 239     private void testEmptyAndNullByteArray() {
 240         sortingHelper.sort(new byte[] {});
 241         sortingHelper.sort(new byte[] {}, 0, 0);
 242 
 243         try {
 244             sortingHelper.sort(null);
 245         } catch (NullPointerException expected) {
 246             try {
 247                 sortingHelper.sort(null, 0, 0);
 248             } catch (NullPointerException expected2) {
 249                 return;
 250             }
 251             fail(sortingHelper + "(byte[],fromIndex,toIndex) shouldn't " +
 252                 "catch null array");
 253         }
 254         fail(sortingHelper + "(byte[]) shouldn't catch null array");
 255     }
 256 
 257     private void testEmptyAndNullCharArray() {
 258         sortingHelper.sort(new char[] {});
 259         sortingHelper.sort(new char[] {}, 0, 0);
 260 
 261         try {
 262             sortingHelper.sort(null);
 263         } catch (NullPointerException expected) {
 264             try {
 265                 sortingHelper.sort(null, 0, 0);
 266             } catch (NullPointerException expected2) {
 267                 return;
 268             }
 269             fail(sortingHelper + "(char[],fromIndex,toIndex) shouldn't " +
 270                 "catch null array");
 271         }
 272         fail(sortingHelper + "(char[]) shouldn't catch null array");
 273     }
 274 
 275     private void testEmptyAndNullShortArray() {
 276         sortingHelper.sort(new short[] {});
 277         sortingHelper.sort(new short[] {}, 0, 0);
 278 
 279         try {
 280             sortingHelper.sort(null);
 281         } catch (NullPointerException expected) {
 282             try {
 283                 sortingHelper.sort(null, 0, 0);
 284             } catch (NullPointerException expected2) {
 285                 return;
 286             }
 287             fail(sortingHelper + "(short[],fromIndex,toIndex) shouldn't " +
 288                 "catch null array");
 289         }
 290         fail(sortingHelper + "(short[]) shouldn't catch null array");
 291     }
 292 
 293     private void testEmptyAndNullFloatArray() {
 294         sortingHelper.sort(new float[] {});
 295         sortingHelper.sort(new float[] {}, 0, 0);
 296 
 297         try {
 298             sortingHelper.sort(null);
 299         } catch (NullPointerException expected) {
 300             try {
 301                 sortingHelper.sort(null, 0, 0);
 302             } catch (NullPointerException expected2) {
 303                 return;
 304             }
 305             fail(sortingHelper + "(float[],fromIndex,toIndex) shouldn't " +
 306                 "catch null array");
 307         }
 308         fail(sortingHelper + "(float[]) shouldn't catch null array");
 309     }
 310 
 311     private void testEmptyAndNullDoubleArray() {
 312         sortingHelper.sort(new double[] {});
 313         sortingHelper.sort(new double[] {}, 0, 0);
 314 
 315         try {
 316             sortingHelper.sort(null);
 317         } catch (NullPointerException expected) {
 318             try {
 319                 sortingHelper.sort(null, 0, 0);
 320             } catch (NullPointerException expected2) {
 321                 return;
 322             }
 323             fail(sortingHelper + "(double[],fromIndex,toIndex) shouldn't " +
 324                 "catch null array");
 325         }
 326         fail(sortingHelper + "(double[]) shouldn't catch null array");
 327     }
 328 
 329     private void testSubArray(int length, TestRandom random) {
 330         if (length < 4) {
 331             return;
 332         }
 333         for (int m = 1; m < length / 2; m <<= 1) {
 334             int fromIndex = m;
 335             int toIndex = length - m;
 336 
 337             prepareSubArray((int[]) gold[0], fromIndex, toIndex);
 338             convertData(length);
 339 
 340             for (int i = 0; i < test.length; i++) {
 341                 printTestName("Test subarray", random, length,
 342                     ", m = " + m + ", " + getType(i));
 343                 sortingHelper.sort(test[i], fromIndex, toIndex);
 344                 checkSubArray(test[i], fromIndex, toIndex);
 345             }
 346         }
 347         out.println();
 348     }
 349 
 350     private void testRange(int length, TestRandom random) {
 351         if (length < 2) {
 352             return;
 353         }
 354         for (int m = 1; m < length; m <<= 1) {
 355             for (int i = 1; i <= length; i++) {
 356                 ((int[]) gold[0]) [i - 1] = i % m + m % i;
 357             }
 358             convertData(length);
 359 
 360             for (int i = 0; i < test.length; i++) {
 361                 printTestName("Test range check", random, length,
 362                     ", m = " + m + ", " + getType(i));
 363                 checkRange(test[i], m);
 364             }
 365         }
 366         out.println();
 367     }
 368 
 369     private void checkSorted(Pair[] a) {
 370         for (int i = 0; i < a.length - 1; i++) {
 371             if (a[i].getKey() > a[i + 1].getKey()) {
 372                 fail("Array is not sorted at " + i + "-th position: " +
 373                     a[i].getKey() + " and " + a[i + 1].getKey());
 374             }
 375         }
 376     }
 377 
 378     private void checkSorted(Point[] a) {
 379         for (int i = 0; i < a.length - 1; i++) {
 380             if (a[i].compareTo(a[i + 1]) > 0) {
 381                 fail("Point array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
 382             }
 383         }
 384     }
 385 
 386     private void checkSorted(Point[] a, Comparator<Point> c) {
 387         for (int i = 0; i < a.length - 1; i++) {
 388             if (c.compare(a[i], a[i + 1]) > 0) {
 389                 fail("Point array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
 390             }
 391         }
 392     }
 393 
 394     private void checkStable(Pair[] a) {
 395         for (int i = 0; i < a.length / 4; ) {
 396             int key1 = a[i].getKey();
 397             int value1 = a[i++].getValue();
 398             int key2 = a[i].getKey();
 399             int value2 = a[i++].getValue();
 400             int key3 = a[i].getKey();
 401             int value3 = a[i++].getValue();
 402             int key4 = a[i].getKey();
 403             int value4 = a[i++].getValue();
 404 
 405             if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
 406                 fail("Keys are different " + key1 + ", " + key2 + ", " +
 407                     key3 + ", " + key4 + " at position " + i);
 408             }
 409             if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
 410                 fail("Sorting is not stable at position " + i +
 411                     ". Second values have been changed: " + value1 + ", " +
 412                     value2 + ", " + value3 + ", " + value4);
 413             }
 414         }
 415     }
 416 
 417     private Pair[] build(int length, Random random) {
 418         Pair[] a = new Pair[length * 4];
 419 
 420         for (int i = 0; i < a.length; ) {
 421             int key = random.nextInt();
 422             a[i++] = new Pair(key, 1);
 423             a[i++] = new Pair(key, 2);
 424             a[i++] = new Pair(key, 3);
 425             a[i++] = new Pair(key, 4);
 426         }
 427         return a;
 428     }
 429 
 430     private void testWithInsertionSort(int length, TestRandom random) {
 431         if (length > 1000) {
 432             return;
 433         }
 434         for (int m = 1; m <= length; m <<= 1) {
 435             for (UnsortedBuilder builder : UnsortedBuilder.values()) {
 436                 builder.build((int[]) gold[0], m, random);
 437                 convertData(length);
 438 
 439                 for (int i = 0; i < test.length; i++) {
 440                     printTestName("Test with insertion sort", random, length,
 441                         ", m = " + m + ", " + getType(i) + " " + builder);
 442                     sortingHelper.sort(test[i]);
 443                     sortByInsertionSort(gold[i]);
 444                     compare(test[i], gold[i]);
 445                 }
 446             }
 447         }
 448         out.println();
 449     }
 450 
 451     private void testMergingSort(int length, TestRandom random) {
 452         if (length < (4 << 10)) { // DualPivotQuicksort.MIN_TRY_MERGE_SIZE
 453             return;
 454         }
 455         final int PERIOD = 50;
 456 
 457         for (int m = PERIOD - 2; m <= PERIOD + 2; m++) {
 458             for (MergingBuilder builder : MergingBuilder.values()) {
 459                 builder.build((int[]) gold[0], m);
 460                 convertData(length);
 461 
 462                 for (int i = 0; i < test.length; i++) {
 463                     printTestName("Test merging sort", random, length,
 464                         ", m = " + m + ", " +  getType(i) + " " + builder);
 465                     sortingHelper.sort(test[i]);
 466                     checkSorted(test[i]);
 467                 }
 468             }
 469         }
 470         out.println();
 471     }
 472 
 473     private void testWithCheckSum(int length, TestRandom random) {
 474         for (int m = 1; m <= length; m <<= 1) {
 475             for (UnsortedBuilder builder : UnsortedBuilder.values()) {
 476                 builder.build((int[]) gold[0], m, random);
 477                 convertData(length);
 478 
 479                 for (int i = 0; i < test.length; i++) {
 480                     printTestName("Test with check sum", random, length,
 481                         ", m = " + m + ", " + getType(i) + " " + builder);
 482                     sortingHelper.sort(test[i]);
 483                     checkWithCheckSum(test[i], gold[i]);
 484                 }
 485             }
 486         }
 487         out.println();
 488     }
 489 
 490     private void testWithScrambling(int length, TestRandom random) {
 491         for (int m = 1; m <= length; m <<= 1) {
 492             for (SortedBuilder builder : SortedBuilder.values()) {
 493                 builder.build((int[]) gold[0], m);
 494                 convertData(length);
 495 
 496                 for (int i = 0; i < test.length; i++) {
 497                     printTestName("Test with scrambling", random, length,
 498                         ", m = " + m + ", " + getType(i) + " " + builder);
 499                     scramble(test[i], random);
 500                     sortingHelper.sort(test[i]);
 501                     compare(test[i], gold[i]);
 502                 }
 503             }
 504         }
 505         out.println();
 506     }
 507 
 508     private void testNegativeZero(int length, TestRandom random) {
 509         for (int i = 5; i < test.length; i++) {
 510             printTestName("Test negative zero -0.0", random, length, " " + getType(i));
 511 
 512             NegativeZeroBuilder builder = NegativeZeroBuilder.values() [i - 5];
 513             builder.build(test[i], random);
 514 
 515             sortingHelper.sort(test[i]);
 516             checkNegativeZero(test[i]);
 517         }
 518         out.println();
 519     }
 520 
 521     private void testFloatingPointSorting(int length, TestRandom random) {
 522         if (length < 2) {
 523             return;
 524         }
 525         final int MAX = 13;
 526 
 527         for (int a = 0; a < MAX; a++) {
 528             for (int g = 0; g < MAX; g++) {
 529                 for (int z = 0; z < MAX; z++) {
 530                     for (int n = 0; n < MAX; n++) {
 531                         for (int p = 0; p < MAX; p++) {
 532                             if (a + g + z + n + p != length) {
 533                                 continue;
 534                             }
 535                             for (int i = 5; i < test.length; i++) {
 536                                 printTestName("Test float-pointing sorting", random, length,
 537                                     ", a = " + a + ", g = " + g + ", z = " + z +
 538                                     ", n = " + n + ", p = " + p + ", " + getType(i));
 539                                 FloatingPointBuilder builder = FloatingPointBuilder.values()[i - 5];
 540                                 builder.build(gold[i], a, g, z, n, p, random);
 541                                 copy(test[i], gold[i]);
 542                                 scramble(test[i], random);
 543                                 sortingHelper.sort(test[i]);
 544                                 compare(test[i], gold[i], a, n, g);
 545                             }
 546                         }
 547                     }
 548                 }
 549             }
 550         }
 551 
 552         for (int m = 13; m > 4; m--) {
 553             int t = length / m;
 554             int g = t, z = t, n = t, p = t;
 555             int a = length - g - z - n - p;
 556 
 557             for (int i = 5; i < test.length; i++) {
 558                 printTestName("Test float-pointing sorting", random, length,
 559                     ", a = " + a + ", g = " + g + ", z = " + z +
 560                     ", n = " + n + ", p = " + p + ", " + getType(i));
 561                 FloatingPointBuilder builder = FloatingPointBuilder.values() [i - 5];
 562                 builder.build(gold[i], a, g, z, n, p, random);
 563                 copy(test[i], gold[i]);
 564                 scramble(test[i], random);
 565                 sortingHelper.sort(test[i]);
 566                 compare(test[i], gold[i], a, n, g);
 567             }
 568         }
 569         out.println();
 570     }
 571 
 572     private void prepareSubArray(int[] a, int fromIndex, int toIndex) {
 573         for (int i = 0; i < fromIndex; i++) {
 574             a[i] = A380;
 575         }
 576         int middle = (fromIndex + toIndex) >>> 1;
 577         int k = 0;
 578 
 579         for (int i = fromIndex; i < middle; i++) {
 580             a[i] = k++;
 581         }
 582 
 583         for (int i = middle; i < toIndex; i++) {
 584             a[i] = k--;
 585         }
 586 
 587         for (int i = toIndex; i < a.length; i++) {
 588             a[i] = B747;
 589         }
 590     }
 591 
 592     private void scramble(Object a, Random random) {
 593         if (a instanceof int[]) {
 594             scramble((int[]) a, random);
 595         } else if (a instanceof long[]) {
 596             scramble((long[]) a, random);
 597         } else if (a instanceof byte[]) {
 598             scramble((byte[]) a, random);
 599         } else if (a instanceof char[]) {
 600             scramble((char[]) a, random);
 601         } else if (a instanceof short[]) {
 602             scramble((short[]) a, random);
 603         } else if (a instanceof float[]) {
 604             scramble((float[]) a, random);
 605         } else if (a instanceof double[]) {
 606             scramble((double[]) a, random);
 607         } else {
 608             fail("Unknown type of array: " + a.getClass().getName());
 609         }
 610     }
 611 
 612     private void scramble(int[] a, Random random) {
 613         for (int i = 0; i < a.length * 7; i++) {
 614             swap(a, random.nextInt(a.length), random.nextInt(a.length));
 615         }
 616     }
 617 
 618     private void scramble(long[] a, Random random) {
 619         for (int i = 0; i < a.length * 7; i++) {
 620             swap(a, random.nextInt(a.length), random.nextInt(a.length));
 621         }
 622     }
 623 
 624     private void scramble(byte[] a, Random random) {
 625         for (int i = 0; i < a.length * 7; i++) {
 626             swap(a, random.nextInt(a.length), random.nextInt(a.length));
 627         }
 628     }
 629 
 630     private void scramble(char[] a, Random random) {
 631         for (int i = 0; i < a.length * 7; i++) {
 632             swap(a, random.nextInt(a.length), random.nextInt(a.length));
 633         }
 634     }
 635 
 636     private void scramble(short[] a, Random random) {
 637         for (int i = 0; i < a.length * 7; i++) {
 638             swap(a, random.nextInt(a.length), random.nextInt(a.length));
 639         }
 640     }
 641 
 642     private void scramble(float[] a, Random random) {
 643         for (int i = 0; i < a.length * 7; i++) {
 644             swap(a, random.nextInt(a.length), random.nextInt(a.length));
 645         }
 646     }
 647 
 648     private void scramble(double[] a, Random random) {
 649         for (int i = 0; i < a.length * 7; i++) {
 650             swap(a, random.nextInt(a.length), random.nextInt(a.length));
 651         }
 652     }
 653 
 654     private void swap(int[] a, int i, int j) {
 655         int t = a[i]; a[i] = a[j]; a[j] = t;
 656     }
 657 
 658     private void swap(long[] a, int i, int j) {
 659         long t = a[i]; a[i] = a[j]; a[j] = t;
 660     }
 661 
 662     private void swap(byte[] a, int i, int j) {
 663         byte t = a[i]; a[i] = a[j]; a[j] = t;
 664     }
 665 
 666     private void swap(char[] a, int i, int j) {
 667         char t = a[i]; a[i] = a[j]; a[j] = t;
 668     }
 669 
 670     private void swap(short[] a, int i, int j) {
 671         short t = a[i]; a[i] = a[j]; a[j] = t;
 672     }
 673 
 674     private void swap(float[] a, int i, int j) {
 675         float t = a[i]; a[i] = a[j]; a[j] = t;
 676     }
 677 
 678     private void swap(double[] a, int i, int j) {
 679         double t = a[i]; a[i] = a[j]; a[j] = t;
 680     }
 681 
 682     private void checkWithCheckSum(Object test, Object gold) {
 683         checkSorted(test);
 684         checkCheckSum(test, gold);
 685     }
 686 
 687     private void fail(String message) {
 688         err.format("\n*** TEST FAILED ***\n\n%s\n\n", message);
 689         throw new RuntimeException("Test failed");
 690     }
 691 
 692     private void checkNegativeZero(Object a) {
 693         if (a instanceof float[]) {
 694             checkNegativeZero((float[]) a);
 695         } else if (a instanceof double[]) {
 696             checkNegativeZero((double[]) a);
 697         } else {
 698             fail("Unknown type of array: " + a.getClass().getName());
 699         }
 700     }
 701 
 702     private void checkNegativeZero(float[] a) {
 703         for (int i = 0; i < a.length - 1; i++) {
 704             if (Float.floatToRawIntBits(a[i]) == 0 && Float.floatToRawIntBits(a[i + 1]) < 0) {
 705                 fail(a[i] + " before " + a[i + 1] + " at position " + i);
 706             }
 707         }
 708     }
 709 
 710     private void checkNegativeZero(double[] a) {
 711         for (int i = 0; i < a.length - 1; i++) {
 712             if (Double.doubleToRawLongBits(a[i]) == 0 && Double.doubleToRawLongBits(a[i + 1]) < 0) {
 713                 fail(a[i] + " before " + a[i + 1] + " at position " + i);
 714             }
 715         }
 716     }
 717 
 718     private void compare(Object a, Object b, int numNaN, int numNeg, int numNegZero) {
 719         if (a instanceof float[]) {
 720             compare((float[]) a, (float[]) b, numNaN, numNeg, numNegZero);
 721         } else if (a instanceof double[]) {
 722             compare((double[]) a, (double[]) b, numNaN, numNeg, numNegZero);
 723         } else {
 724             fail("Unknown type of array: " + a.getClass().getName());
 725         }
 726     }
 727 
 728     private void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {
 729         for (int i = a.length - numNaN; i < a.length; i++) {
 730             if (a[i] == a[i]) {
 731                 fail("There must be NaN instead of " + a[i] + " at position " + i);
 732             }
 733         }
 734         final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
 735 
 736         for (int i = numNeg; i < numNeg + numNegZero; i++) {
 737             if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {
 738                 fail("There must be -0.0 instead of " + a[i] + " at position " + i);
 739             }
 740         }
 741 
 742         for (int i = 0; i < a.length - numNaN; i++) {
 743             if (a[i] != b[i]) {
 744                 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 745             }
 746         }
 747     }
 748 
 749     private void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {
 750         for (int i = a.length - numNaN; i < a.length; i++) {
 751             if (a[i] == a[i]) {
 752                 fail("There must be NaN instead of " + a[i] + " at position " + i);
 753             }
 754         }
 755         final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
 756 
 757         for (int i = numNeg; i < numNeg + numNegZero; i++) {
 758             if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) {
 759                 fail("There must be -0.0 instead of " + a[i] + " at position " + i);
 760             }
 761         }
 762 
 763         for (int i = 0; i < a.length - numNaN; i++) {
 764             if (a[i] != b[i]) {
 765                 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 766             }
 767         }
 768     }
 769 
 770     private void compare(Object a, Object b) {
 771         if (a instanceof int[]) {
 772             compare((int[]) a, (int[]) b);
 773         } else if (a instanceof long[]) {
 774             compare((long[]) a, (long[]) b);
 775         } else if (a instanceof byte[]) {
 776             compare((byte[]) a, (byte[]) b);
 777         } else if (a instanceof char[]) {
 778             compare((char[]) a, (char[]) b);
 779         } else if (a instanceof short[]) {
 780             compare((short[]) a, (short[]) b);
 781         } else if (a instanceof float[]) {
 782             compare((float[]) a, (float[]) b);
 783         } else if (a instanceof double[]) {
 784             compare((double[]) a, (double[]) b);
 785         } else {
 786             fail("Unknown type of array: " + a.getClass().getName());
 787         }
 788     }
 789 
 790     private void compare(int[] a, int[] b) {
 791         for (int i = 0; i < a.length; i++) {
 792             if (a[i] != b[i]) {
 793                 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 794             }
 795         }
 796     }
 797 
 798     private void compare(long[] a, long[] b) {
 799         for (int i = 0; i < a.length; i++) {
 800             if (a[i] != b[i]) {
 801                 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 802             }
 803         }
 804     }
 805 
 806     private void compare(byte[] a, byte[] b) {
 807         for (int i = 0; i < a.length; i++) {
 808             if (a[i] != b[i]) {
 809                 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 810             }
 811         }
 812     }
 813 
 814     private void compare(char[] a, char[] b) {
 815         for (int i = 0; i < a.length; i++) {
 816             if (a[i] != b[i]) {
 817                 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 818             }
 819         }
 820     }
 821 
 822     private void compare(short[] a, short[] b) {
 823         for (int i = 0; i < a.length; i++) {
 824             if (a[i] != b[i]) {
 825                 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 826             }
 827         }
 828     }
 829 
 830     private void compare(float[] a, float[] b) {
 831         for (int i = 0; i < a.length; i++) {
 832             if (a[i] != b[i]) {
 833                 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 834             }
 835         }
 836     }
 837 
 838     private void compare(double[] a, double[] b) {
 839         for (int i = 0; i < a.length; i++) {
 840             if (a[i] != b[i]) {
 841                 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 842             }
 843         }
 844     }
 845 
 846     private String getType(int i) {
 847         Object a = test[i];
 848 
 849         if (a instanceof int[]) {
 850             return "INT   ";
 851         }
 852         if (a instanceof long[]) {
 853             return "LONG  ";
 854         }
 855         if (a instanceof byte[]) {
 856             return "BYTE  ";
 857         }
 858         if (a instanceof char[]) {
 859             return "CHAR  ";
 860         }
 861         if (a instanceof short[]) {
 862             return "SHORT ";
 863         }
 864         if (a instanceof float[]) {
 865             return "FLOAT ";
 866         }
 867         if (a instanceof double[]) {
 868             return "DOUBLE";
 869         }
 870         fail("Unknown type of array: " + a.getClass().getName());
 871         return null;
 872     }
 873 
 874     private void checkSorted(Object a) {
 875         if (a instanceof int[]) {
 876             checkSorted((int[]) a);
 877         } else if (a instanceof long[]) {
 878             checkSorted((long[]) a);
 879         } else if (a instanceof byte[]) {
 880             checkSorted((byte[]) a);
 881         } else if (a instanceof char[]) {
 882             checkSorted((char[]) a);
 883         } else if (a instanceof short[]) {
 884             checkSorted((short[]) a);
 885         } else if (a instanceof float[]) {
 886             checkSorted((float[]) a);
 887         } else if (a instanceof double[]) {
 888             checkSorted((double[]) a);
 889         } else {
 890             fail("Unknown type of array: " + a.getClass().getName());
 891         }
 892     }
 893 
 894     private void checkSorted(int[] a) {
 895         for (int i = 0; i < a.length - 1; i++) {
 896             if (a[i] > a[i + 1]) {
 897                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
 898             }
 899         }
 900     }
 901 
 902     private void checkSorted(long[] a) {
 903         for (int i = 0; i < a.length - 1; i++) {
 904             if (a[i] > a[i + 1]) {
 905                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
 906             }
 907         }
 908     }
 909 
 910     private void checkSorted(byte[] a) {
 911         for (int i = 0; i < a.length - 1; i++) {
 912             if (a[i] > a[i + 1]) {
 913                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
 914             }
 915         }
 916     }
 917 
 918     private void checkSorted(char[] a) {
 919         for (int i = 0; i < a.length - 1; i++) {
 920             if (a[i] > a[i + 1]) {
 921                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
 922             }
 923         }
 924     }
 925 
 926     private void checkSorted(short[] a) {
 927         for (int i = 0; i < a.length - 1; i++) {
 928             if (a[i] > a[i + 1]) {
 929                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
 930             }
 931         }
 932     }
 933 
 934     private void checkSorted(float[] a) {
 935         for (int i = 0; i < a.length - 1; i++) {
 936             if (a[i] > a[i + 1]) {
 937                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
 938             }
 939         }
 940     }
 941 
 942     private void checkSorted(double[] a) {
 943         for (int i = 0; i < a.length - 1; i++) {
 944             if (a[i] > a[i + 1]) {
 945                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
 946             }
 947         }
 948     }
 949 
 950     private void checkCheckSum(Object test, Object gold) {
 951         if (checkSumXor(test) != checkSumXor(gold)) {
 952             fail("Original and sorted arrays are not identical [^]");
 953         }
 954         if (checkSumPlus(test) != checkSumPlus(gold)) {
 955             fail("Original and sorted arrays are not identical [+]");
 956         }
 957     }
 958 
 959     private int checkSumXor(Object a) {
 960         if (a instanceof int[]) {
 961             return checkSumXor((int[]) a);
 962         }
 963         if (a instanceof long[]) {
 964             return checkSumXor((long[]) a);
 965         }
 966         if (a instanceof byte[]) {
 967             return checkSumXor((byte[]) a);
 968         }
 969         if (a instanceof char[]) {
 970             return checkSumXor((char[]) a);
 971         }
 972         if (a instanceof short[]) {
 973             return checkSumXor((short[]) a);
 974         }
 975         if (a instanceof float[]) {
 976             return checkSumXor((float[]) a);
 977         }
 978         if (a instanceof double[]) {
 979             return checkSumXor((double[]) a);
 980         }
 981         fail("Unknown type of array: " + a.getClass().getName());
 982         return -1;
 983     }
 984 
 985     private int checkSumXor(int[] a) {
 986         int checkSum = 0;
 987 
 988         for (int e : a) {
 989             checkSum ^= e;
 990         }
 991         return checkSum;
 992     }
 993 
 994     private int checkSumXor(long[] a) {
 995         long checkSum = 0;
 996 
 997         for (long e : a) {
 998             checkSum ^= e;
 999         }
1000         return (int) checkSum;
1001     }
1002 
1003     private int checkSumXor(byte[] a) {
1004         byte checkSum = 0;
1005 
1006         for (byte e : a) {
1007             checkSum ^= e;
1008         }
1009         return (int) checkSum;
1010     }
1011 
1012     private int checkSumXor(char[] a) {
1013         char checkSum = 0;
1014 
1015         for (char e : a) {
1016             checkSum ^= e;
1017         }
1018         return (int) checkSum;
1019     }
1020 
1021     private int checkSumXor(short[] a) {
1022         short checkSum = 0;
1023 
1024         for (short e : a) {
1025             checkSum ^= e;
1026         }
1027         return (int) checkSum;
1028     }
1029 
1030     private int checkSumXor(float[] a) {
1031         int checkSum = 0;
1032 
1033         for (float e : a) {
1034             checkSum ^= (int) e;
1035         }
1036         return checkSum;
1037     }
1038 
1039     private int checkSumXor(double[] a) {
1040         int checkSum = 0;
1041 
1042         for (double e : a) {
1043             checkSum ^= (int) e;
1044         }
1045         return checkSum;
1046     }
1047 
1048     private int checkSumPlus(Object a) {
1049         if (a instanceof int[]) {
1050             return checkSumPlus((int[]) a);
1051         }
1052         if (a instanceof long[]) {
1053             return checkSumPlus((long[]) a);
1054         }
1055         if (a instanceof byte[]) {
1056             return checkSumPlus((byte[]) a);
1057         }
1058         if (a instanceof char[]) {
1059             return checkSumPlus((char[]) a);
1060         }
1061         if (a instanceof short[]) {
1062             return checkSumPlus((short[]) a);
1063         }
1064         if (a instanceof float[]) {
1065             return checkSumPlus((float[]) a);
1066         }
1067         if (a instanceof double[]) {
1068             return checkSumPlus((double[]) a);
1069         }
1070         fail("Unknown type of array: " + a.getClass().getName());
1071         return -1;
1072     }
1073 
1074     private int checkSumPlus(int[] a) {
1075         int checkSum = 0;
1076 
1077         for (int e : a) {
1078             checkSum += e;
1079         }
1080         return checkSum;
1081     }
1082 
1083     private int checkSumPlus(long[] a) {
1084         long checkSum = 0;
1085 
1086         for (long e : a) {
1087             checkSum += e;
1088         }
1089         return (int) checkSum;
1090     }
1091 
1092     private int checkSumPlus(byte[] a) {
1093         byte checkSum = 0;
1094 
1095         for (byte e : a) {
1096             checkSum += e;
1097         }
1098         return (int) checkSum;
1099     }
1100 
1101     private int checkSumPlus(char[] a) {
1102         char checkSum = 0;
1103 
1104         for (char e : a) {
1105             checkSum += e;
1106         }
1107         return (int) checkSum;
1108     }
1109 
1110     private int checkSumPlus(short[] a) {
1111         short checkSum = 0;
1112 
1113         for (short e : a) {
1114             checkSum += e;
1115         }
1116         return (int) checkSum;
1117     }
1118 
1119     private int checkSumPlus(float[] a) {
1120         int checkSum = 0;
1121 
1122         for (float e : a) {
1123             checkSum += (int) e;
1124         }
1125         return checkSum;
1126     }
1127 
1128     private int checkSumPlus(double[] a) {
1129         int checkSum = 0;
1130 
1131         for (double e : a) {
1132             checkSum += (int) e;
1133         }
1134         return checkSum;
1135     }
1136 
1137     private void sortByInsertionSort(Object a) {
1138         if (a instanceof int[]) {
1139             sortByInsertionSort((int[]) a);
1140         } else if (a instanceof long[]) {
1141             sortByInsertionSort((long[]) a);
1142         } else if (a instanceof byte[]) {
1143             sortByInsertionSort((byte[]) a);
1144         } else if (a instanceof char[]) {
1145             sortByInsertionSort((char[]) a);
1146         } else if (a instanceof short[]) {
1147             sortByInsertionSort((short[]) a);
1148         } else if (a instanceof float[]) {
1149             sortByInsertionSort((float[]) a);
1150         } else if (a instanceof double[]) {
1151             sortByInsertionSort((double[]) a);
1152         } else {
1153             fail("Unknown type of array: " + a.getClass().getName());
1154         }
1155     }
1156 
1157     private void sortByInsertionSort(int[] a) {
1158         for (int j, i = 1; i < a.length; i++) {
1159             int ai = a[i];
1160 
1161             for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1162                 a[j + 1] = a[j];
1163             }
1164             a[j + 1] = ai;
1165         }
1166     }
1167 
1168     private void sortByInsertionSort(long[] a) {
1169         for (int j, i = 1; i < a.length; i++) {
1170             long ai = a[i];
1171 
1172             for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1173                 a[j + 1] = a[j];
1174             }
1175             a[j + 1] = ai;
1176         }
1177     }
1178 
1179     private void sortByInsertionSort(byte[] a) {
1180         for (int j, i = 1; i < a.length; i++) {
1181             byte ai = a[i];
1182 
1183             for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1184                 a[j + 1] = a[j];
1185             }
1186             a[j + 1] = ai;
1187         }
1188     }
1189 
1190     private void sortByInsertionSort(char[] a) {
1191         for (int j, i = 1; i < a.length; i++) {
1192             char ai = a[i];
1193 
1194             for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1195                 a[j + 1] = a[j];
1196             }
1197             a[j + 1] = ai;
1198         }
1199     }
1200 
1201     private void sortByInsertionSort(short[] a) {
1202         for (int j, i = 1; i < a.length; i++) {
1203             short ai = a[i];
1204 
1205             for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1206                 a[j + 1] = a[j];
1207             }
1208             a[j + 1] = ai;
1209         }
1210     }
1211 
1212     private void sortByInsertionSort(float[] a) {
1213         for (int j, i = 1; i < a.length; i++) {
1214             float ai = a[i];
1215 
1216             for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1217                 a[j + 1] = a[j];
1218             }
1219             a[j + 1] = ai;
1220         }
1221     }
1222 
1223     private void sortByInsertionSort(double[] a) {
1224         for (int j, i = 1; i < a.length; i++) {
1225             double ai = a[i];
1226 
1227             for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1228                 a[j + 1] = a[j];
1229             }
1230             a[j + 1] = ai;
1231         }
1232     }
1233 
1234     private void checkSubArray(Object a, int fromIndex, int toIndex) {
1235         if (a instanceof int[]) {
1236             checkSubArray((int[]) a, fromIndex, toIndex);
1237         } else if (a instanceof long[]) {
1238             checkSubArray((long[]) a, fromIndex, toIndex);
1239         } else if (a instanceof byte[]) {
1240             checkSubArray((byte[]) a, fromIndex, toIndex);
1241         } else if (a instanceof char[]) {
1242             checkSubArray((char[]) a, fromIndex, toIndex);
1243         } else if (a instanceof short[]) {
1244             checkSubArray((short[]) a, fromIndex, toIndex);
1245         } else if (a instanceof float[]) {
1246             checkSubArray((float[]) a, fromIndex, toIndex);
1247         } else if (a instanceof double[]) {
1248             checkSubArray((double[]) a, fromIndex, toIndex);
1249         } else {
1250             fail("Unknown type of array: " + a.getClass().getName());
1251         }
1252     }
1253 
1254     private void checkSubArray(int[] a, int fromIndex, int toIndex) {
1255         for (int i = 0; i < fromIndex; i++) {
1256             if (a[i] != A380) {
1257                 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1258             }
1259         }
1260 
1261         for (int i = fromIndex; i < toIndex - 1; i++) {
1262             if (a[i] > a[i + 1]) {
1263                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1264             }
1265         }
1266 
1267         for (int i = toIndex; i < a.length; i++) {
1268             if (a[i] != B747) {
1269                 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1270             }
1271         }
1272     }
1273 
1274     private void checkSubArray(long[] a, int fromIndex, int toIndex) {
1275         for (int i = 0; i < fromIndex; i++) {
1276             if (a[i] != (long) A380) {
1277                 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1278             }
1279         }
1280 
1281         for (int i = fromIndex; i < toIndex - 1; i++) {
1282             if (a[i] > a[i + 1]) {
1283                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1284             }
1285         }
1286 
1287         for (int i = toIndex; i < a.length; i++) {
1288             if (a[i] != (long) B747) {
1289                 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1290             }
1291         }
1292     }
1293 
1294     private void checkSubArray(byte[] a, int fromIndex, int toIndex) {
1295         for (int i = 0; i < fromIndex; i++) {
1296             if (a[i] != (byte) A380) {
1297                 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1298             }
1299         }
1300 
1301         for (int i = fromIndex; i < toIndex - 1; i++) {
1302             if (a[i] > a[i + 1]) {
1303                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1304             }
1305         }
1306 
1307         for (int i = toIndex; i < a.length; i++) {
1308             if (a[i] != (byte) B747) {
1309                 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1310             }
1311         }
1312     }
1313 
1314     private void checkSubArray(char[] a, int fromIndex, int toIndex) {
1315         for (int i = 0; i < fromIndex; i++) {
1316             if (a[i] != (char) A380) {
1317                 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1318             }
1319         }
1320 
1321         for (int i = fromIndex; i < toIndex - 1; i++) {
1322             if (a[i] > a[i + 1]) {
1323                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1324             }
1325         }
1326 
1327         for (int i = toIndex; i < a.length; i++) {
1328             if (a[i] != (char) B747) {
1329                 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1330             }
1331         }
1332     }
1333 
1334     private void checkSubArray(short[] a, int fromIndex, int toIndex) {
1335         for (int i = 0; i < fromIndex; i++) {
1336             if (a[i] != (short) A380) {
1337                 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1338             }
1339         }
1340 
1341         for (int i = fromIndex; i < toIndex - 1; i++) {
1342             if (a[i] > a[i + 1]) {
1343                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1344             }
1345         }
1346 
1347         for (int i = toIndex; i < a.length; i++) {
1348             if (a[i] != (short) B747) {
1349                 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1350             }
1351         }
1352     }
1353 
1354     private void checkSubArray(float[] a, int fromIndex, int toIndex) {
1355         for (int i = 0; i < fromIndex; i++) {
1356             if (a[i] != (float) A380) {
1357                 fail("Range sort changes left element at position " + i + hex((long) a[i], A380));
1358             }
1359         }
1360 
1361         for (int i = fromIndex; i < toIndex - 1; i++) {
1362             if (a[i] > a[i + 1]) {
1363                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1364             }
1365         }
1366 
1367         for (int i = toIndex; i < a.length; i++) {
1368             if (a[i] != (float) B747) {
1369                 fail("Range sort changes right element at position " + i + hex((long) a[i], B747));
1370             }
1371         }
1372     }
1373 
1374     private void checkSubArray(double[] a, int fromIndex, int toIndex) {
1375         for (int i = 0; i < fromIndex; i++) {
1376             if (a[i] != (double) A380) {
1377                 fail("Range sort changes left element at position " + i + hex((long) a[i], A380));
1378             }
1379         }
1380 
1381         for (int i = fromIndex; i < toIndex - 1; i++) {
1382             if (a[i] > a[i + 1]) {
1383                 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1384             }
1385         }
1386 
1387         for (int i = toIndex; i < a.length; i++) {
1388             if (a[i] != (double) B747) {
1389                 fail("Range sort changes right element at position " + i + hex((long) a[i], B747));
1390             }
1391         }
1392     }
1393 
1394     private void checkRange(Object a, int m) {
1395         if (a instanceof int[]) {
1396             checkRange((int[]) a, m);
1397         } else if (a instanceof long[]) {
1398             checkRange((long[]) a, m);
1399         } else if (a instanceof byte[]) {
1400             checkRange((byte[]) a, m);
1401         } else if (a instanceof char[]) {
1402             checkRange((char[]) a, m);
1403         } else if (a instanceof short[]) {
1404             checkRange((short[]) a, m);
1405         } else if (a instanceof float[]) {
1406             checkRange((float[]) a, m);
1407         } else if (a instanceof double[]) {
1408             checkRange((double[]) a, m);
1409         } else {
1410             fail("Unknown type of array: " + a.getClass().getName());
1411         }
1412     }
1413 
1414     private void checkRange(int[] a, int m) {
1415         try {
1416             sortingHelper.sort(a, m + 1, m);
1417             fail(sortingHelper + " does not throw IllegalArgumentException " +
1418                 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1419         } catch (IllegalArgumentException iae) {
1420             try {
1421                 sortingHelper.sort(a, -m, a.length);
1422                 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1423                     "as expected: fromIndex = " + (-m));
1424             } catch (ArrayIndexOutOfBoundsException aoe) {
1425                 try {
1426                     sortingHelper.sort(a, 0, a.length + m);
1427                     fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1428                         "as expected: toIndex = " + (a.length + m));
1429                 } catch (ArrayIndexOutOfBoundsException expected) {}
1430             }
1431         }
1432     }
1433 
1434     private void checkRange(long[] a, int m) {
1435         try {
1436             sortingHelper.sort(a, m + 1, m);
1437             fail(sortingHelper + " does not throw IllegalArgumentException " +
1438                 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1439         } catch (IllegalArgumentException iae) {
1440             try {
1441                 sortingHelper.sort(a, -m, a.length);
1442                 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1443                     "as expected: fromIndex = " + (-m));
1444             } catch (ArrayIndexOutOfBoundsException aoe) {
1445                 try {
1446                     sortingHelper.sort(a, 0, a.length + m);
1447                     fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1448                         "as expected: toIndex = " + (a.length + m));
1449                 } catch (ArrayIndexOutOfBoundsException expected) {}
1450             }
1451         }
1452     }
1453 
1454     private void checkRange(byte[] a, int m) {
1455         try {
1456             sortingHelper.sort(a, m + 1, m);
1457             fail(sortingHelper + " does not throw IllegalArgumentException " +
1458                 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1459         } catch (IllegalArgumentException iae) {
1460             try {
1461                 sortingHelper.sort(a, -m, a.length);
1462                 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1463                     "as expected: fromIndex = " + (-m));
1464             } catch (ArrayIndexOutOfBoundsException aoe) {
1465                 try {
1466                     sortingHelper.sort(a, 0, a.length + m);
1467                     fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1468                         "as expected: toIndex = " + (a.length + m));
1469                 } catch (ArrayIndexOutOfBoundsException expected) {}
1470             }
1471         }
1472     }
1473 
1474     private void checkRange(char[] a, int m) {
1475         try {
1476             sortingHelper.sort(a, m + 1, m);
1477             fail(sortingHelper + " does not throw IllegalArgumentException " +
1478                 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1479         } catch (IllegalArgumentException iae) {
1480             try {
1481                 sortingHelper.sort(a, -m, a.length);
1482                 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1483                     "as expected: fromIndex = " + (-m));
1484             } catch (ArrayIndexOutOfBoundsException aoe) {
1485                 try {
1486                     sortingHelper.sort(a, 0, a.length + m);
1487                     fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1488                         "as expected: toIndex = " + (a.length + m));
1489                 } catch (ArrayIndexOutOfBoundsException expected) {}
1490             }
1491         }
1492     }
1493 
1494     private void checkRange(short[] a, int m) {
1495         try {
1496             sortingHelper.sort(a, m + 1, m);
1497             fail(sortingHelper + " does not throw IllegalArgumentException " +
1498                 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1499         } catch (IllegalArgumentException iae) {
1500             try {
1501                 sortingHelper.sort(a, -m, a.length);
1502                 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1503                     "as expected: fromIndex = " + (-m));
1504             } catch (ArrayIndexOutOfBoundsException aoe) {
1505                 try {
1506                     sortingHelper.sort(a, 0, a.length + m);
1507                     fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1508                         "as expected: toIndex = " + (a.length + m));
1509                 } catch (ArrayIndexOutOfBoundsException expected) {}
1510             }
1511         }
1512     }
1513 
1514     private void checkRange(float[] a, int m) {
1515         try {
1516             sortingHelper.sort(a, m + 1, m);
1517             fail(sortingHelper + " does not throw IllegalArgumentException " +
1518                 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1519         } catch (IllegalArgumentException iae) {
1520             try {
1521                 sortingHelper.sort(a, -m, a.length);
1522                 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1523                     "as expected: fromIndex = " + (-m));
1524             } catch (ArrayIndexOutOfBoundsException aoe) {
1525                 try {
1526                     sortingHelper.sort(a, 0, a.length + m);
1527                     fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1528                         "as expected: toIndex = " + (a.length + m));
1529                 } catch (ArrayIndexOutOfBoundsException expected) {}
1530             }
1531         }
1532     }
1533 
1534     private void checkRange(double[] a, int m) {
1535         try {
1536             sortingHelper.sort(a, m + 1, m);
1537             fail(sortingHelper + " does not throw IllegalArgumentException " +
1538                 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1539         } catch (IllegalArgumentException iae) {
1540             try {
1541                 sortingHelper.sort(a, -m, a.length);
1542                 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1543                     "as expected: fromIndex = " + (-m));
1544             } catch (ArrayIndexOutOfBoundsException aoe) {
1545                 try {
1546                     sortingHelper.sort(a, 0, a.length + m);
1547                     fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1548                         "as expected: toIndex = " + (a.length + m));
1549                 } catch (ArrayIndexOutOfBoundsException expected) {}
1550             }
1551         }
1552     }
1553 
1554     private void copy(Object dst, Object src) {
1555         if (src instanceof float[]) {
1556             copy((float[]) dst, (float[]) src);
1557         } else if (src instanceof double[]) {
1558             copy((double[]) dst, (double[]) src);
1559         } else {
1560             fail("Unknown type of array: " + src.getClass().getName());
1561         }
1562     }
1563 
1564     private void copy(float[] dst, float[] src) {
1565         System.arraycopy(src, 0, dst, 0, src.length);
1566     }
1567 
1568     private void copy(double[] dst, double[] src) {
1569         System.arraycopy(src, 0, dst, 0, src.length);
1570     }
1571 
1572     private void printTestName(String test, TestRandom random, int length) {
1573         printTestName(test, random, length, "");
1574     }
1575 
1576     private void createData(int length) {
1577         gold = new Object[] {
1578             new int[length], new long[length],
1579             new byte[length], new char[length], new short[length],
1580             new float[length], new double[length]
1581         };
1582 
1583         test = new Object[] {
1584             new int[length], new long[length],
1585             new byte[length], new char[length], new short[length],
1586             new float[length], new double[length]
1587         };
1588     }
1589 
1590     private void convertData(int length) {
1591         for (int i = 1; i < gold.length; i++) {
1592             TypeConverter converter = TypeConverter.values()[i - 1];
1593             converter.convert((int[])gold[0], gold[i]);
1594         }
1595 
1596         for (int i = 0; i < gold.length; i++) {
1597             System.arraycopy(gold[i], 0, test[i], 0, length);
1598         }
1599     }
1600 
1601     private String hex(long a, int b) {
1602         return ": " + Long.toHexString(a) + ", must be " + Integer.toHexString(b);
1603     }
1604 
1605     private void printTestName(String test, TestRandom random, int length, String message) {
1606         out.println( "[" + sortingHelper + "] '" + test +
1607             "' length = " + length + ", random = " + random + message);
1608     }
1609 
1610     private static enum TypeConverter {
1611         LONG {
1612             void convert(int[] src, Object dst) {
1613                 long[] b = (long[]) dst;
1614 
1615                 for (int i = 0; i < src.length; i++) {
1616                     b[i] = (long) src[i];
1617                 }
1618             }
1619         },
1620 
1621         BYTE {
1622             void convert(int[] src, Object dst) {
1623                 byte[] b = (byte[]) dst;
1624 
1625                 for (int i = 0; i < src.length; i++) {
1626                     b[i] = (byte) src[i];
1627                 }
1628             }
1629         },
1630 
1631         CHAR {
1632             void convert(int[] src, Object dst) {
1633                 char[] b = (char[]) dst;
1634 
1635                 for (int i = 0; i < src.length; i++) {
1636                     b[i] = (char) src[i];
1637                 }
1638             }
1639         },
1640 
1641         SHORT {
1642             void convert(int[] src, Object dst) {
1643                 short[] b = (short[]) dst;
1644 
1645                 for (int i = 0; i < src.length; i++) {
1646                     b[i] = (short) src[i];
1647                 }
1648             }
1649         },
1650 
1651         FLOAT {
1652             void convert(int[] src, Object dst) {
1653                 float[] b = (float[]) dst;
1654 
1655                 for (int i = 0; i < src.length; i++) {
1656                     b[i] = (float) src[i];
1657                 }
1658             }
1659         },
1660 
1661         DOUBLE {
1662             void convert(int[] src, Object dst) {
1663                 double[] b = (double[]) dst;
1664 
1665                 for (int i = 0; i < src.length; i++) {
1666                     b[i] = (double) src[i];
1667                 }
1668             }
1669         };
1670 
1671         abstract void convert(int[] src, Object dst);
1672     }
1673 
1674     private static enum SortedBuilder {
1675         STEPS {
1676             void build(int[] a, int m) {
1677                 for (int i = 0; i < m; i++) {
1678                     a[i] = 0;
1679                 }
1680 
1681                 for (int i = m; i < a.length; i++) {
1682                     a[i] = 1;
1683                 }
1684             }
1685         };
1686 
1687         abstract void build(int[] a, int m);
1688     }
1689 
1690     private static enum UnsortedBuilder {
1691         RANDOM {
1692             void build(int[] a, int m, Random random) {
1693                 for (int i = 0; i < a.length; i++) {
1694                     a[i] = random.nextInt();
1695                 }
1696             }
1697         },
1698 
1699         ASCENDING {
1700             void build(int[] a, int m, Random random) {
1701                 for (int i = 0; i < a.length; i++) {
1702                     a[i] = m + i;
1703                 }
1704             }
1705         },
1706 
1707         DESCENDING {
1708             void build(int[] a, int m, Random random) {
1709                 for (int i = 0; i < a.length; i++) {
1710                     a[i] = a.length - m - i;
1711                 }
1712             }
1713         },
1714 
1715         EQUAL {
1716             void build(int[] a, int m, Random random) {
1717                 for (int i = 0; i < a.length; i++) {
1718                     a[i] = m;
1719                 }
1720             }
1721         },
1722 
1723         SAW {
1724             void build(int[] a, int m, Random random) {
1725                 int incCount = 1;
1726                 int decCount = a.length;
1727                 int i = 0;
1728                 int period = m--;
1729 
1730                 while (true) {
1731                     for (int k = 1; k <= period; k++) {
1732                         if (i >= a.length) {
1733                             return;
1734                         }
1735                         a[i++] = incCount++;
1736                     }
1737                     period += m;
1738 
1739                     for (int k = 1; k <= period; k++) {
1740                         if (i >= a.length) {
1741                             return;
1742                         }
1743                         a[i++] = decCount--;
1744                     }
1745                     period += m;
1746                 }
1747             }
1748         },
1749 
1750         REPEATED {
1751             void build(int[] a, int m, Random random) {
1752                 for (int i = 0; i < a.length; i++) {
1753                     a[i] = i % m;
1754                 }
1755             }
1756         },
1757 
1758         DUPLICATED {
1759             void build(int[] a, int m, Random random) {
1760                 for (int i = 0; i < a.length; i++) {
1761                     a[i] = random.nextInt(m);
1762                 }
1763             }
1764         },
1765 
1766         ORGAN_PIPES {
1767             void build(int[] a, int m, Random random) {
1768                 int middle = a.length / (m + 1);
1769 
1770                 for (int i = 0; i < middle; i++) {
1771                     a[i] = i;
1772                 }
1773 
1774                 for (int i = middle; i < a.length; i++) {
1775                     a[i] = a.length - i - 1;
1776                 }
1777             }
1778         },
1779 
1780         STAGGER {
1781             void build(int[] a, int m, Random random) {
1782                 for (int i = 0; i < a.length; i++) {
1783                     a[i] = (i * m + i) % a.length;
1784                 }
1785             }
1786         },
1787 
1788         PLATEAU {
1789             void build(int[] a, int m, Random random) {
1790                 for (int i = 0; i < a.length; i++) {
1791                     a[i] = Math.min(i, m);
1792                 }
1793             }
1794         },
1795 
1796         SHUFFLE {
1797             void build(int[] a, int m, Random random) {
1798                 int x = 0, y = 0;
1799 
1800                 for (int i = 0; i < a.length; i++) {
1801                     a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
1802                 }
1803             }
1804         },
1805 
1806         LATCH {
1807             void build(int[] a, int m, Random random) {
1808                 int max = a.length / m;
1809                 max = max < 2 ? 2 : max;
1810 
1811                 for (int i = 0; i < a.length; i++) {
1812                     a[i] = i % max;
1813                 }
1814             }
1815         };
1816 
1817         abstract void build(int[] a, int m, Random random);
1818     }
1819 
1820     private static enum MergingBuilder {
1821         ASCENDING {
1822             void build(int[] a, int m) {
1823                 int period = a.length / m;
1824                 int v = 1, i = 0;
1825 
1826                 for (int k = 0; k < m; k++) {
1827                     v = 1;
1828 
1829                     for (int p = 0; p < period; p++) {
1830                         a[i++] = v++;
1831                     }
1832                 }
1833 
1834                 for (int j = i; j < a.length - 1; j++) {
1835                     a[j] = v++;
1836                 }
1837 
1838                 a[a.length - 1] = 0;
1839             }
1840         },
1841 
1842         DESCENDING {
1843             void build(int[] a, int m) {
1844                 int period = a.length / m;
1845                 int v = -1, i = 0;
1846 
1847                 for (int k = 0; k < m; k++) {
1848                     v = -1;
1849 
1850                     for (int p = 0; p < period; p++) {
1851                         a[i++] = v--;
1852                     }
1853                 }
1854 
1855                 for (int j = i; j < a.length - 1; j++) {
1856                     a[j] = v--;
1857                 }
1858 
1859                 a[a.length - 1] = 0;
1860             }
1861         },
1862 
1863         POINT {
1864             void build(int[] a, int m) {
1865                 for (int i = 0; i < a.length; i++) {
1866                     a[i] = 0;
1867                 }
1868                 a[a.length / 2] = m;
1869             }
1870         },
1871 
1872         LINE {
1873             void build(int[] a, int m) {
1874                 for (int i = 0; i < a.length; i++) {
1875                     a[i] = i;
1876                 }
1877                 reverse(a, 0, a.length - 1);
1878             }
1879         },
1880 
1881         PEARL {
1882             void build(int[] a, int m) {
1883                 for (int i = 0; i < a.length; i++) {
1884                     a[i] = i;
1885                 }
1886                 reverse(a, 0, 2);
1887             }
1888         },
1889 
1890         RING {
1891             void build(int[] a, int m) {
1892                 int k1 = a.length / 3;
1893                 int k2 = a.length / 3 * 2;
1894                 int level = a.length / 3;
1895 
1896                 for (int i = 0, k = level; i < k1; i++) {
1897                     a[i] = k--;
1898                 }
1899 
1900                 for (int i = k1; i < k2; i++) {
1901                     a[i] = 0;
1902                 }
1903 
1904                 for (int i = k2, k = level; i < a.length; i++) {
1905                     a[i] = k--;
1906                 }
1907             }
1908         };
1909 
1910         abstract void build(int[] a, int m);
1911 
1912         private static void reverse(int[] a, int lo, int hi) {
1913             for (--hi; lo < hi; ) {
1914                 int tmp = a[lo];
1915                 a[lo++] = a[hi];
1916                 a[hi--] = tmp;
1917             }
1918         }
1919     }
1920 
1921     private static enum NegativeZeroBuilder {
1922         FLOAT {
1923             void build(Object o, Random random) {
1924                 float[] a = (float[]) o;
1925 
1926                 for (int i = 0; i < a.length; i++) {
1927                     a[i] = random.nextBoolean() ? -0.0f : 0.0f;
1928                 }
1929             }
1930         },
1931 
1932         DOUBLE {
1933             void build(Object o, Random random) {
1934                 double[] a = (double[]) o;
1935 
1936                 for (int i = 0; i < a.length; i++) {
1937                     a[i] = random.nextBoolean() ? -0.0d : 0.0d;
1938                 }
1939             }
1940         };
1941 
1942         abstract void build(Object o, Random random);
1943     }
1944 
1945     private static enum FloatingPointBuilder {
1946         FLOAT {
1947             void build(Object o, int a, int g, int z, int n, int p, Random random) {
1948                 float negativeValue = -random.nextFloat();
1949                 float positiveValue =  random.nextFloat();
1950                 float[] x = (float[]) o;
1951                 int fromIndex = 0;
1952 
1953                 writeValue(x, negativeValue, fromIndex, n);
1954                 fromIndex += n;
1955 
1956                 writeValue(x, -0.0f, fromIndex, g);
1957                 fromIndex += g;
1958 
1959                 writeValue(x, 0.0f, fromIndex, z);
1960                 fromIndex += z;
1961 
1962                 writeValue(x, positiveValue, fromIndex, p);
1963                 fromIndex += p;
1964 
1965                 writeValue(x, Float.NaN, fromIndex, a);
1966             }
1967         },
1968 
1969         DOUBLE {
1970             void build(Object o, int a, int g, int z, int n, int p, Random random) {
1971                 double negativeValue = -random.nextFloat();
1972                 double positiveValue =  random.nextFloat();
1973                 double[] x = (double[]) o;
1974                 int fromIndex = 0;
1975 
1976                 writeValue(x, negativeValue, fromIndex, n);
1977                 fromIndex += n;
1978 
1979                 writeValue(x, -0.0d, fromIndex, g);
1980                 fromIndex += g;
1981 
1982                 writeValue(x, 0.0d, fromIndex, z);
1983                 fromIndex += z;
1984 
1985                 writeValue(x, positiveValue, fromIndex, p);
1986                 fromIndex += p;
1987 
1988                 writeValue(x, Double.NaN, fromIndex, a);
1989             }
1990         };
1991 
1992         abstract void build(Object o, int a, int g, int z, int n, int p, Random random);
1993 
1994         private static void writeValue(float[] a, float value, int fromIndex, int count) {
1995             for (int i = fromIndex; i < fromIndex + count; i++) {
1996                 a[i] = value;
1997             }
1998         }
1999 
2000         private static void writeValue(double[] a, double value, int fromIndex, int count) {
2001             for (int i = fromIndex; i < fromIndex + count; i++) {
2002                 a[i] = value;
2003             }
2004         }
2005     }
2006 
2007     private static Comparator<Pair> pairComparator = new Comparator<Pair>() {
2008 
2009         @Override
2010         public int compare(Pair p1, Pair p2) {
2011             return p1.compareTo(p2);
2012         }
2013     };
2014 
2015     private static class Pair implements Comparable<Pair> {
2016 
2017         private Pair(int key, int value) {
2018             this.key = key;
2019             this.value = value;
2020         }
2021 
2022         int getKey() {
2023             return key;
2024         }
2025 
2026         int getValue() {
2027             return value;
2028         }
2029 
2030         @Override
2031         public int compareTo(Pair pair) {
2032             return Integer.compare(key, pair.key);
2033         }
2034 
2035         @Override
2036         public String toString() {
2037             return "(" + key + ", " + value + ")";
2038         }
2039 
2040         private int key;
2041         private int value;
2042     }
2043 
2044     private static class TestRandom extends Random {
2045 
2046         private static final TestRandom BABA = new TestRandom(0xBABA);
2047         private static final TestRandom DEDA = new TestRandom(0xDEDA);
2048         private static final TestRandom C0FFEE = new TestRandom(0xC0FFEE);
2049 
2050         private TestRandom(long seed) {
2051             super(seed);
2052             this.seed = Long.toHexString(seed).toUpperCase();
2053         }
2054 
2055         @Override
2056         public String toString() {
2057             return seed;
2058         }
2059 
2060         private String seed;
2061     }
2062 }
--- EOF ---