1 /*
   2  * Copyright (c) 2012, 2013, 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.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 package java.util;
  26 
  27 import java.util.concurrent.RecursiveAction;
  28 import java.util.concurrent.CountedCompleter;
  29 
  30 /**
  31  * Helper utilities for the parallel sort methods in Arrays.parallelSort.
  32  *
  33  * For each primitive type, plus Object, we define a static class to
  34  * contain the Sorter and Merger implementations for that type:
  35  *
  36  * Sorter classes based mainly on CilkSort
  37  * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
  38  * Basic algorithm:
  39  * if array size is small, just use a sequential quicksort (via Arrays.sort)
  40  *         Otherwise:
  41  *         1. Break array in half.
  42  *         2. For each half,
  43  *             a. break the half in half (i.e., quarters),
  44  *             b. sort the quarters
  45  *             c. merge them together
  46  *         3. merge together the two halves.
  47  *
  48  * One reason for splitting in quarters is that this guarantees that
  49  * the final sort is in the main array, not the workspace array.
  50  * (workspace and main swap roles on each subsort step.)  Leaf-level
  51  * sorts use the associated sequential sort.
  52  *
  53  * Merger classes perform merging for Sorter.  They are structured
  54  * such that if the underlying sort is stable (as is true for
  55  * TimSort), then so is the full sort.  If big enough, they split the
  56  * largest of the two partitions in half, find the greatest point in
  57  * smaller partition less than the beginning of the second half of
  58  * larger via binary search; and then merge in parallel the two
  59  * partitions.  In part to ensure tasks are triggered in
  60  * stability-preserving order, the current CountedCompleter design
  61  * requires some little tasks to serve as place holders for triggering
  62  * completion tasks.  These classes (EmptyCompleter and Relay) don't
  63  * need to keep track of the arrays, and are never themselves forked,
  64  * so don't hold any task state.
  65  *
  66  * The primitive class versions (FJByte... FJDouble) are
  67  * identical to each other except for type declarations.
  68  *
  69  * The base sequential sorts rely on non-public versions of TimSort,
  70  * ComparableTimSort, and DualPivotQuicksort sort methods that accept
  71  * temp workspace array slices that we will have already allocated, so
  72  * avoids redundant allocation. (Except for DualPivotQuicksort byte[]
  73  * sort, that does not ever use a workspace array.)
  74  */
  75 /*package*/ class ArraysParallelSortHelpers {
  76 
  77     /*
  78      * Style note: The task classes have a lot of parameters, that are
  79      * stored as task fields and copied to local variables and used in
  80      * compute() methods, We pack these into as few lines as possible,
  81      * and hoist consistency checks among them before main loops, to
  82      * reduce distraction.
  83      */
  84 
  85     /**
  86      * A placeholder task for Sorters, used for the lowest
  87      * quartile task, that does not need to maintain array state.
  88      */
  89     static final class EmptyCompleter extends CountedCompleter<Void> {
  90         static final long serialVersionUID = 2446542900576103244L;
  91         EmptyCompleter(CountedCompleter<?> p) { super(p); }
  92         public final void compute() { }
  93     }
  94 
  95     /**
  96      * A trigger for secondary merge of two merges
  97      */
  98     static final class Relay extends CountedCompleter<Void> {
  99         static final long serialVersionUID = 2446542900576103244L;
 100         final CountedCompleter<?> task;
 101         Relay(CountedCompleter<?> task) {
 102             super(null, 1);
 103             this.task = task;
 104         }
 105         public final void compute() { }
 106         public final void onCompletion(CountedCompleter<?> t) {
 107             task.compute();
 108         }
 109     }
 110 
 111     /** Object + Comparator support class */
 112     static final class FJObject {
 113         static final class Sorter<T> extends CountedCompleter<Void> {
 114             static final long serialVersionUID = 2446542900576103244L;
 115             final T[] a, w;
 116             final int base, size, wbase, gran;
 117             Comparator<? super T> comparator;
 118             Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
 119                    int wbase, int gran,
 120                    Comparator<? super T> comparator) {
 121                 super(par);
 122                 this.a = a; this.w = w; this.base = base; this.size = size;
 123                 this.wbase = wbase; this.gran = gran;
 124                 this.comparator = comparator;
 125             }
 126             public final void compute() {
 127                 CountedCompleter<?> s = this;
 128                 Comparator<? super T> c = this.comparator;
 129                 T[] a = this.a, w = this.w; // localize all params
 130                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
 131                 while (n > g) {
 132                     int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
 133                     Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
 134                                                       wb+h, n-h, b, g, c));
 135                     Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
 136                                                       b+u, n-u, wb+h, g, c));
 137                     new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
 138                     new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();;
 139                     Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
 140                                                       b+q, h-q, wb, g, c));
 141                     new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
 142                     s = new EmptyCompleter(bc);
 143                     n = q;
 144                 }
 145                 TimSort.sort(a, b, b + n, c, w, wb, n);
 146                 s.tryComplete();
 147             }
 148         }
 149 
 150         static final class Merger<T> extends CountedCompleter<Void> {
 151             static final long serialVersionUID = 2446542900576103244L;
 152             final T[] a, w; // main and workspace arrays
 153             final int lbase, lsize, rbase, rsize, wbase, gran;
 154             Comparator<? super T> comparator;
 155             Merger(CountedCompleter<?> par, T[] a, T[] w,
 156                    int lbase, int lsize, int rbase,
 157                    int rsize, int wbase, int gran,
 158                    Comparator<? super T> comparator) {
 159                 super(par);
 160                 this.a = a; this.w = w;
 161                 this.lbase = lbase; this.lsize = lsize;
 162                 this.rbase = rbase; this.rsize = rsize;
 163                 this.wbase = wbase; this.gran = gran;
 164                 this.comparator = comparator;
 165             }
 166 
 167             public final void compute() {
 168                 Comparator<? super T> c = this.comparator;
 169                 T[] a = this.a, w = this.w; // localize all params
 170                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
 171                     rn = this.rsize, k = this.wbase, g = this.gran;
 172                 if (a == null || w == null || lb < 0 || rb < 0 || k < 0 ||
 173                     c == null)
 174                     throw new IllegalStateException(); // hoist checks
 175                 for (int lh, rh;;) {  // split larger, find point in smaller
 176                     if (ln >= rn) {
 177                         if (ln <= g)
 178                             break;
 179                         rh = rn;
 180                         T split = a[(lh = ln >>> 1) + lb];
 181                         for (int lo = 0; lo < rh; ) {
 182                             int rm = (lo + rh) >>> 1;
 183                             if (c.compare(split, a[rm + rb]) <= 0)
 184                                 rh = rm;
 185                             else
 186                                 lo = rm + 1;
 187                         }
 188                     }
 189                     else {
 190                         if (rn <= g)
 191                             break;
 192                         lh = ln;
 193                         T split = a[(rh = rn >>> 1) + rb];
 194                         for (int lo = 0; lo < lh; ) {
 195                             int lm = (lo + lh) >>> 1;
 196                             if (c.compare(split, a[lm + lb]) <= 0)
 197                                 lh = lm;
 198                             else
 199                                 lo = lm + 1;
 200                         }
 201                     }
 202                     Merger<T> m = new Merger<>(this, a, w, lb + lh, ln - lh,
 203                                                rb + rh, rn - rh,
 204                                                k + lh + rh, g, c);
 205                     rn = rh;
 206                     ln = lh;
 207                     addToPendingCount(1);
 208                     m.fork();
 209                 }
 210 
 211                 int lf = lb + ln, rf = rb + rn; // index bounds
 212                 while (lb < lf && rb < rf) {
 213                     T t, al, ar;
 214                     if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) {
 215                         lb++; t = al;
 216                     }
 217                     else {
 218                         rb++; t = ar;
 219                     }
 220                     w[k++] = t;
 221                 }
 222                 if (rb < rf)
 223                     System.arraycopy(a, rb, w, k, rf - rb);
 224                 else if (lb < lf)
 225                     System.arraycopy(a, lb, w, k, lf - lb);
 226 
 227                 tryComplete();
 228             }
 229 
 230         }
 231     } // FJObject
 232 
 233     /** byte support class */
 234     static final class FJByte {
 235         static final class Sorter extends CountedCompleter<Void> {
 236             static final long serialVersionUID = 2446542900576103244L;
 237             final byte[] a, w;
 238             final int base, size, wbase, gran;
 239             Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base,
 240                    int size, int wbase, int gran) {
 241                 super(par);
 242                 this.a = a; this.w = w; this.base = base; this.size = size;
 243                 this.wbase = wbase; this.gran = gran;
 244             }
 245             public final void compute() {
 246                 CountedCompleter<?> s = this;
 247                 byte[] a = this.a, w = this.w; // localize all params
 248                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
 249                 while (n > g) {
 250                     int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
 251                     Relay fc = new Relay(new Merger(s, w, a, wb, h,
 252                                                     wb+h, n-h, b, g));
 253                     Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
 254                                                     b+u, n-u, wb+h, g));
 255                     new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
 256                     new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
 257                     Relay bc = new Relay(new Merger(fc, a, w, b, q,
 258                                                     b+q, h-q, wb, g));
 259                     new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
 260                     s = new EmptyCompleter(bc);
 261                     n = q;
 262                 }
 263                 DualPivotQuicksort.sort(a, b, b + n - 1);
 264                 s.tryComplete();
 265             }
 266         }
 267 
 268         static final class Merger extends CountedCompleter<Void> {
 269             static final long serialVersionUID = 2446542900576103244L;
 270             final byte[] a, w; // main and workspace arrays
 271             final int lbase, lsize, rbase, rsize, wbase, gran;
 272             Merger(CountedCompleter<?> par, byte[] a, byte[] w,
 273                    int lbase, int lsize, int rbase,
 274                    int rsize, int wbase, int gran) {
 275                 super(par);
 276                 this.a = a; this.w = w;
 277                 this.lbase = lbase; this.lsize = lsize;
 278                 this.rbase = rbase; this.rsize = rsize;
 279                 this.wbase = wbase; this.gran = gran;
 280             }
 281 
 282             public final void compute() {
 283                 byte[] a = this.a, w = this.w; // localize all params
 284                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
 285                     rn = this.rsize, k = this.wbase, g = this.gran;
 286                 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
 287                     throw new IllegalStateException(); // hoist checks
 288                 for (int lh, rh;;) {  // split larger, find point in smaller
 289                     if (ln >= rn) {
 290                         if (ln <= g)
 291                             break;
 292                         rh = rn;
 293                         byte split = a[(lh = ln >>> 1) + lb];
 294                         for (int lo = 0; lo < rh; ) {
 295                             int rm = (lo + rh) >>> 1;
 296                             if (split <= a[rm + rb])
 297                                 rh = rm;
 298                             else
 299                                 lo = rm + 1;
 300                         }
 301                     }
 302                     else {
 303                         if (rn <= g)
 304                             break;
 305                         lh = ln;
 306                         byte split = a[(rh = rn >>> 1) + rb];
 307                         for (int lo = 0; lo < lh; ) {
 308                             int lm = (lo + lh) >>> 1;
 309                             if (split <= a[lm + lb])
 310                                 lh = lm;
 311                             else
 312                                 lo = lm + 1;
 313                         }
 314                     }
 315                     Merger m = new Merger(this, a, w, lb + lh, ln - lh,
 316                                           rb + rh, rn - rh,
 317                                           k + lh + rh, g);
 318                     rn = rh;
 319                     ln = lh;
 320                     addToPendingCount(1);
 321                     m.fork();
 322                 }
 323 
 324                 int lf = lb + ln, rf = rb + rn; // index bounds
 325                 while (lb < lf && rb < rf) {
 326                     byte t, al, ar;
 327                     if ((al = a[lb]) <= (ar = a[rb])) {
 328                         lb++; t = al;
 329                     }
 330                     else {
 331                         rb++; t = ar;
 332                     }
 333                     w[k++] = t;
 334                 }
 335                 if (rb < rf)
 336                     System.arraycopy(a, rb, w, k, rf - rb);
 337                 else if (lb < lf)
 338                     System.arraycopy(a, lb, w, k, lf - lb);
 339                 tryComplete();
 340             }
 341         }
 342     } // FJByte
 343 
 344     /** char support class */
 345     static final class FJChar {
 346         static final class Sorter extends CountedCompleter<Void> {
 347             static final long serialVersionUID = 2446542900576103244L;
 348             final char[] a, w;
 349             final int base, size, wbase, gran;
 350             Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
 351                    int size, int wbase, int gran) {
 352                 super(par);
 353                 this.a = a; this.w = w; this.base = base; this.size = size;
 354                 this.wbase = wbase; this.gran = gran;
 355             }
 356             public final void compute() {
 357                 CountedCompleter<?> s = this;
 358                 char[] a = this.a, w = this.w; // localize all params
 359                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
 360                 while (n > g) {
 361                     int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
 362                     Relay fc = new Relay(new Merger(s, w, a, wb, h,
 363                                                     wb+h, n-h, b, g));
 364                     Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
 365                                                     b+u, n-u, wb+h, g));
 366                     new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
 367                     new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
 368                     Relay bc = new Relay(new Merger(fc, a, w, b, q,
 369                                                     b+q, h-q, wb, g));
 370                     new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
 371                     s = new EmptyCompleter(bc);
 372                     n = q;
 373                 }
 374                 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
 375                 s.tryComplete();
 376             }
 377         }
 378 
 379         static final class Merger extends CountedCompleter<Void> {
 380             static final long serialVersionUID = 2446542900576103244L;
 381             final char[] a, w; // main and workspace arrays
 382             final int lbase, lsize, rbase, rsize, wbase, gran;
 383             Merger(CountedCompleter<?> par, char[] a, char[] w,
 384                    int lbase, int lsize, int rbase,
 385                    int rsize, int wbase, int gran) {
 386                 super(par);
 387                 this.a = a; this.w = w;
 388                 this.lbase = lbase; this.lsize = lsize;
 389                 this.rbase = rbase; this.rsize = rsize;
 390                 this.wbase = wbase; this.gran = gran;
 391             }
 392 
 393             public final void compute() {
 394                 char[] a = this.a, w = this.w; // localize all params
 395                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
 396                     rn = this.rsize, k = this.wbase, g = this.gran;
 397                 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
 398                     throw new IllegalStateException(); // hoist checks
 399                 for (int lh, rh;;) {  // split larger, find point in smaller
 400                     if (ln >= rn) {
 401                         if (ln <= g)
 402                             break;
 403                         rh = rn;
 404                         char split = a[(lh = ln >>> 1) + lb];
 405                         for (int lo = 0; lo < rh; ) {
 406                             int rm = (lo + rh) >>> 1;
 407                             if (split <= a[rm + rb])
 408                                 rh = rm;
 409                             else
 410                                 lo = rm + 1;
 411                         }
 412                     }
 413                     else {
 414                         if (rn <= g)
 415                             break;
 416                         lh = ln;
 417                         char split = a[(rh = rn >>> 1) + rb];
 418                         for (int lo = 0; lo < lh; ) {
 419                             int lm = (lo + lh) >>> 1;
 420                             if (split <= a[lm + lb])
 421                                 lh = lm;
 422                             else
 423                                 lo = lm + 1;
 424                         }
 425                     }
 426                     Merger m = new Merger(this, a, w, lb + lh, ln - lh,
 427                                           rb + rh, rn - rh,
 428                                           k + lh + rh, g);
 429                     rn = rh;
 430                     ln = lh;
 431                     addToPendingCount(1);
 432                     m.fork();
 433                 }
 434 
 435                 int lf = lb + ln, rf = rb + rn; // index bounds
 436                 while (lb < lf && rb < rf) {
 437                     char t, al, ar;
 438                     if ((al = a[lb]) <= (ar = a[rb])) {
 439                         lb++; t = al;
 440                     }
 441                     else {
 442                         rb++; t = ar;
 443                     }
 444                     w[k++] = t;
 445                 }
 446                 if (rb < rf)
 447                     System.arraycopy(a, rb, w, k, rf - rb);
 448                 else if (lb < lf)
 449                     System.arraycopy(a, lb, w, k, lf - lb);
 450                 tryComplete();
 451             }
 452         }
 453     } // FJChar
 454 
 455     /** short support class */
 456     static final class FJShort {
 457         static final class Sorter extends CountedCompleter<Void> {
 458             static final long serialVersionUID = 2446542900576103244L;
 459             final short[] a, w;
 460             final int base, size, wbase, gran;
 461             Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
 462                    int size, int wbase, int gran) {
 463                 super(par);
 464                 this.a = a; this.w = w; this.base = base; this.size = size;
 465                 this.wbase = wbase; this.gran = gran;
 466             }
 467             public final void compute() {
 468                 CountedCompleter<?> s = this;
 469                 short[] a = this.a, w = this.w; // localize all params
 470                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
 471                 while (n > g) {
 472                     int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
 473                     Relay fc = new Relay(new Merger(s, w, a, wb, h,
 474                                                     wb+h, n-h, b, g));
 475                     Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
 476                                                     b+u, n-u, wb+h, g));
 477                     new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
 478                     new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
 479                     Relay bc = new Relay(new Merger(fc, a, w, b, q,
 480                                                     b+q, h-q, wb, g));
 481                     new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
 482                     s = new EmptyCompleter(bc);
 483                     n = q;
 484                 }
 485                 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
 486                 s.tryComplete();
 487             }
 488         }
 489 
 490         static final class Merger extends CountedCompleter<Void> {
 491             static final long serialVersionUID = 2446542900576103244L;
 492             final short[] a, w; // main and workspace arrays
 493             final int lbase, lsize, rbase, rsize, wbase, gran;
 494             Merger(CountedCompleter<?> par, short[] a, short[] w,
 495                    int lbase, int lsize, int rbase,
 496                    int rsize, int wbase, int gran) {
 497                 super(par);
 498                 this.a = a; this.w = w;
 499                 this.lbase = lbase; this.lsize = lsize;
 500                 this.rbase = rbase; this.rsize = rsize;
 501                 this.wbase = wbase; this.gran = gran;
 502             }
 503 
 504             public final void compute() {
 505                 short[] a = this.a, w = this.w; // localize all params
 506                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
 507                     rn = this.rsize, k = this.wbase, g = this.gran;
 508                 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
 509                     throw new IllegalStateException(); // hoist checks
 510                 for (int lh, rh;;) {  // split larger, find point in smaller
 511                     if (ln >= rn) {
 512                         if (ln <= g)
 513                             break;
 514                         rh = rn;
 515                         short split = a[(lh = ln >>> 1) + lb];
 516                         for (int lo = 0; lo < rh; ) {
 517                             int rm = (lo + rh) >>> 1;
 518                             if (split <= a[rm + rb])
 519                                 rh = rm;
 520                             else
 521                                 lo = rm + 1;
 522                         }
 523                     }
 524                     else {
 525                         if (rn <= g)
 526                             break;
 527                         lh = ln;
 528                         short split = a[(rh = rn >>> 1) + rb];
 529                         for (int lo = 0; lo < lh; ) {
 530                             int lm = (lo + lh) >>> 1;
 531                             if (split <= a[lm + lb])
 532                                 lh = lm;
 533                             else
 534                                 lo = lm + 1;
 535                         }
 536                     }
 537                     Merger m = new Merger(this, a, w, lb + lh, ln - lh,
 538                                           rb + rh, rn - rh,
 539                                           k + lh + rh, g);
 540                     rn = rh;
 541                     ln = lh;
 542                     addToPendingCount(1);
 543                     m.fork();
 544                 }
 545 
 546                 int lf = lb + ln, rf = rb + rn; // index bounds
 547                 while (lb < lf && rb < rf) {
 548                     short t, al, ar;
 549                     if ((al = a[lb]) <= (ar = a[rb])) {
 550                         lb++; t = al;
 551                     }
 552                     else {
 553                         rb++; t = ar;
 554                     }
 555                     w[k++] = t;
 556                 }
 557                 if (rb < rf)
 558                     System.arraycopy(a, rb, w, k, rf - rb);
 559                 else if (lb < lf)
 560                     System.arraycopy(a, lb, w, k, lf - lb);
 561                 tryComplete();
 562             }
 563         }
 564     } // FJShort
 565 
 566     /** int support class */
 567     static final class FJInt {
 568         static final class Sorter extends CountedCompleter<Void> {
 569             static final long serialVersionUID = 2446542900576103244L;
 570             final int[] a, w;
 571             final int base, size, wbase, gran;
 572             Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
 573                    int size, int wbase, int gran) {
 574                 super(par);
 575                 this.a = a; this.w = w; this.base = base; this.size = size;
 576                 this.wbase = wbase; this.gran = gran;
 577             }
 578             public final void compute() {
 579                 CountedCompleter<?> s = this;
 580                 int[] a = this.a, w = this.w; // localize all params
 581                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
 582                 while (n > g) {
 583                     int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
 584                     Relay fc = new Relay(new Merger(s, w, a, wb, h,
 585                                                     wb+h, n-h, b, g));
 586                     Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
 587                                                     b+u, n-u, wb+h, g));
 588                     new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
 589                     new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
 590                     Relay bc = new Relay(new Merger(fc, a, w, b, q,
 591                                                     b+q, h-q, wb, g));
 592                     new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
 593                     s = new EmptyCompleter(bc);
 594                     n = q;
 595                 }
 596                 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
 597                 s.tryComplete();
 598             }
 599         }
 600 
 601         static final class Merger extends CountedCompleter<Void> {
 602             static final long serialVersionUID = 2446542900576103244L;
 603             final int[] a, w; // main and workspace arrays
 604             final int lbase, lsize, rbase, rsize, wbase, gran;
 605             Merger(CountedCompleter<?> par, int[] a, int[] w,
 606                    int lbase, int lsize, int rbase,
 607                    int rsize, int wbase, int gran) {
 608                 super(par);
 609                 this.a = a; this.w = w;
 610                 this.lbase = lbase; this.lsize = lsize;
 611                 this.rbase = rbase; this.rsize = rsize;
 612                 this.wbase = wbase; this.gran = gran;
 613             }
 614 
 615             public final void compute() {
 616                 int[] a = this.a, w = this.w; // localize all params
 617                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
 618                     rn = this.rsize, k = this.wbase, g = this.gran;
 619                 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
 620                     throw new IllegalStateException(); // hoist checks
 621                 for (int lh, rh;;) {  // split larger, find point in smaller
 622                     if (ln >= rn) {
 623                         if (ln <= g)
 624                             break;
 625                         rh = rn;
 626                         int split = a[(lh = ln >>> 1) + lb];
 627                         for (int lo = 0; lo < rh; ) {
 628                             int rm = (lo + rh) >>> 1;
 629                             if (split <= a[rm + rb])
 630                                 rh = rm;
 631                             else
 632                                 lo = rm + 1;
 633                         }
 634                     }
 635                     else {
 636                         if (rn <= g)
 637                             break;
 638                         lh = ln;
 639                         int split = a[(rh = rn >>> 1) + rb];
 640                         for (int lo = 0; lo < lh; ) {
 641                             int lm = (lo + lh) >>> 1;
 642                             if (split <= a[lm + lb])
 643                                 lh = lm;
 644                             else
 645                                 lo = lm + 1;
 646                         }
 647                     }
 648                     Merger m = new Merger(this, a, w, lb + lh, ln - lh,
 649                                           rb + rh, rn - rh,
 650                                           k + lh + rh, g);
 651                     rn = rh;
 652                     ln = lh;
 653                     addToPendingCount(1);
 654                     m.fork();
 655                 }
 656 
 657                 int lf = lb + ln, rf = rb + rn; // index bounds
 658                 while (lb < lf && rb < rf) {
 659                     int t, al, ar;
 660                     if ((al = a[lb]) <= (ar = a[rb])) {
 661                         lb++; t = al;
 662                     }
 663                     else {
 664                         rb++; t = ar;
 665                     }
 666                     w[k++] = t;
 667                 }
 668                 if (rb < rf)
 669                     System.arraycopy(a, rb, w, k, rf - rb);
 670                 else if (lb < lf)
 671                     System.arraycopy(a, lb, w, k, lf - lb);
 672                 tryComplete();
 673             }
 674         }
 675     } // FJInt
 676 
 677     /** long support class */
 678     static final class FJLong {
 679         static final class Sorter extends CountedCompleter<Void> {
 680             static final long serialVersionUID = 2446542900576103244L;
 681             final long[] a, w;
 682             final int base, size, wbase, gran;
 683             Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
 684                    int size, int wbase, int gran) {
 685                 super(par);
 686                 this.a = a; this.w = w; this.base = base; this.size = size;
 687                 this.wbase = wbase; this.gran = gran;
 688             }
 689             public final void compute() {
 690                 CountedCompleter<?> s = this;
 691                 long[] a = this.a, w = this.w; // localize all params
 692                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
 693                 while (n > g) {
 694                     int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
 695                     Relay fc = new Relay(new Merger(s, w, a, wb, h,
 696                                                     wb+h, n-h, b, g));
 697                     Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
 698                                                     b+u, n-u, wb+h, g));
 699                     new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
 700                     new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
 701                     Relay bc = new Relay(new Merger(fc, a, w, b, q,
 702                                                     b+q, h-q, wb, g));
 703                     new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
 704                     s = new EmptyCompleter(bc);
 705                     n = q;
 706                 }
 707                 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
 708                 s.tryComplete();
 709             }
 710         }
 711 
 712         static final class Merger extends CountedCompleter<Void> {
 713             static final long serialVersionUID = 2446542900576103244L;
 714             final long[] a, w; // main and workspace arrays
 715             final int lbase, lsize, rbase, rsize, wbase, gran;
 716             Merger(CountedCompleter<?> par, long[] a, long[] w,
 717                    int lbase, int lsize, int rbase,
 718                    int rsize, int wbase, int gran) {
 719                 super(par);
 720                 this.a = a; this.w = w;
 721                 this.lbase = lbase; this.lsize = lsize;
 722                 this.rbase = rbase; this.rsize = rsize;
 723                 this.wbase = wbase; this.gran = gran;
 724             }
 725 
 726             public final void compute() {
 727                 long[] a = this.a, w = this.w; // localize all params
 728                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
 729                     rn = this.rsize, k = this.wbase, g = this.gran;
 730                 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
 731                     throw new IllegalStateException(); // hoist checks
 732                 for (int lh, rh;;) {  // split larger, find point in smaller
 733                     if (ln >= rn) {
 734                         if (ln <= g)
 735                             break;
 736                         rh = rn;
 737                         long split = a[(lh = ln >>> 1) + lb];
 738                         for (int lo = 0; lo < rh; ) {
 739                             int rm = (lo + rh) >>> 1;
 740                             if (split <= a[rm + rb])
 741                                 rh = rm;
 742                             else
 743                                 lo = rm + 1;
 744                         }
 745                     }
 746                     else {
 747                         if (rn <= g)
 748                             break;
 749                         lh = ln;
 750                         long split = a[(rh = rn >>> 1) + rb];
 751                         for (int lo = 0; lo < lh; ) {
 752                             int lm = (lo + lh) >>> 1;
 753                             if (split <= a[lm + lb])
 754                                 lh = lm;
 755                             else
 756                                 lo = lm + 1;
 757                         }
 758                     }
 759                     Merger m = new Merger(this, a, w, lb + lh, ln - lh,
 760                                           rb + rh, rn - rh,
 761                                           k + lh + rh, g);
 762                     rn = rh;
 763                     ln = lh;
 764                     addToPendingCount(1);
 765                     m.fork();
 766                 }
 767 
 768                 int lf = lb + ln, rf = rb + rn; // index bounds
 769                 while (lb < lf && rb < rf) {
 770                     long t, al, ar;
 771                     if ((al = a[lb]) <= (ar = a[rb])) {
 772                         lb++; t = al;
 773                     }
 774                     else {
 775                         rb++; t = ar;
 776                     }
 777                     w[k++] = t;
 778                 }
 779                 if (rb < rf)
 780                     System.arraycopy(a, rb, w, k, rf - rb);
 781                 else if (lb < lf)
 782                     System.arraycopy(a, lb, w, k, lf - lb);
 783                 tryComplete();
 784             }
 785         }
 786     } // FJLong
 787 
 788     /** float support class */
 789     static final class FJFloat {
 790         static final class Sorter extends CountedCompleter<Void> {
 791             static final long serialVersionUID = 2446542900576103244L;
 792             final float[] a, w;
 793             final int base, size, wbase, gran;
 794             Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
 795                    int size, int wbase, int gran) {
 796                 super(par);
 797                 this.a = a; this.w = w; this.base = base; this.size = size;
 798                 this.wbase = wbase; this.gran = gran;
 799             }
 800             public final void compute() {
 801                 CountedCompleter<?> s = this;
 802                 float[] a = this.a, w = this.w; // localize all params
 803                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
 804                 while (n > g) {
 805                     int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
 806                     Relay fc = new Relay(new Merger(s, w, a, wb, h,
 807                                                     wb+h, n-h, b, g));
 808                     Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
 809                                                     b+u, n-u, wb+h, g));
 810                     new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
 811                     new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
 812                     Relay bc = new Relay(new Merger(fc, a, w, b, q,
 813                                                     b+q, h-q, wb, g));
 814                     new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
 815                     s = new EmptyCompleter(bc);
 816                     n = q;
 817                 }
 818                 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
 819                 s.tryComplete();
 820             }
 821         }
 822 
 823         static final class Merger extends CountedCompleter<Void> {
 824             static final long serialVersionUID = 2446542900576103244L;
 825             final float[] a, w; // main and workspace arrays
 826             final int lbase, lsize, rbase, rsize, wbase, gran;
 827             Merger(CountedCompleter<?> par, float[] a, float[] w,
 828                    int lbase, int lsize, int rbase,
 829                    int rsize, int wbase, int gran) {
 830                 super(par);
 831                 this.a = a; this.w = w;
 832                 this.lbase = lbase; this.lsize = lsize;
 833                 this.rbase = rbase; this.rsize = rsize;
 834                 this.wbase = wbase; this.gran = gran;
 835             }
 836 
 837             public final void compute() {
 838                 float[] a = this.a, w = this.w; // localize all params
 839                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
 840                     rn = this.rsize, k = this.wbase, g = this.gran;
 841                 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
 842                     throw new IllegalStateException(); // hoist checks
 843                 for (int lh, rh;;) {  // split larger, find point in smaller
 844                     if (ln >= rn) {
 845                         if (ln <= g)
 846                             break;
 847                         rh = rn;
 848                         float split = a[(lh = ln >>> 1) + lb];
 849                         for (int lo = 0; lo < rh; ) {
 850                             int rm = (lo + rh) >>> 1;
 851                             if (split <= a[rm + rb])
 852                                 rh = rm;
 853                             else
 854                                 lo = rm + 1;
 855                         }
 856                     }
 857                     else {
 858                         if (rn <= g)
 859                             break;
 860                         lh = ln;
 861                         float split = a[(rh = rn >>> 1) + rb];
 862                         for (int lo = 0; lo < lh; ) {
 863                             int lm = (lo + lh) >>> 1;
 864                             if (split <= a[lm + lb])
 865                                 lh = lm;
 866                             else
 867                                 lo = lm + 1;
 868                         }
 869                     }
 870                     Merger m = new Merger(this, a, w, lb + lh, ln - lh,
 871                                           rb + rh, rn - rh,
 872                                           k + lh + rh, g);
 873                     rn = rh;
 874                     ln = lh;
 875                     addToPendingCount(1);
 876                     m.fork();
 877                 }
 878 
 879                 int lf = lb + ln, rf = rb + rn; // index bounds
 880                 while (lb < lf && rb < rf) {
 881                     float t, al, ar;
 882                     if ((al = a[lb]) <= (ar = a[rb])) {
 883                         lb++; t = al;
 884                     }
 885                     else {
 886                         rb++; t = ar;
 887                     }
 888                     w[k++] = t;
 889                 }
 890                 if (rb < rf)
 891                     System.arraycopy(a, rb, w, k, rf - rb);
 892                 else if (lb < lf)
 893                     System.arraycopy(a, lb, w, k, lf - lb);
 894                 tryComplete();
 895             }
 896         }
 897     } // FJFloat
 898 
 899     /** double support class */
 900     static final class FJDouble {
 901         static final class Sorter extends CountedCompleter<Void> {
 902             static final long serialVersionUID = 2446542900576103244L;
 903             final double[] a, w;
 904             final int base, size, wbase, gran;
 905             Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
 906                    int size, int wbase, int gran) {
 907                 super(par);
 908                 this.a = a; this.w = w; this.base = base; this.size = size;
 909                 this.wbase = wbase; this.gran = gran;
 910             }
 911             public final void compute() {
 912                 CountedCompleter<?> s = this;
 913                 double[] a = this.a, w = this.w; // localize all params
 914                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
 915                 while (n > g) {
 916                     int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
 917                     Relay fc = new Relay(new Merger(s, w, a, wb, h,
 918                                                     wb+h, n-h, b, g));
 919                     Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
 920                                                     b+u, n-u, wb+h, g));
 921                     new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
 922                     new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
 923                     Relay bc = new Relay(new Merger(fc, a, w, b, q,
 924                                                     b+q, h-q, wb, g));
 925                     new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
 926                     s = new EmptyCompleter(bc);
 927                     n = q;
 928                 }
 929                 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
 930                 s.tryComplete();
 931             }
 932         }
 933 
 934         static final class Merger extends CountedCompleter<Void> {
 935             static final long serialVersionUID = 2446542900576103244L;
 936             final double[] a, w; // main and workspace arrays
 937             final int lbase, lsize, rbase, rsize, wbase, gran;
 938             Merger(CountedCompleter<?> par, double[] a, double[] w,
 939                    int lbase, int lsize, int rbase,
 940                    int rsize, int wbase, int gran) {
 941                 super(par);
 942                 this.a = a; this.w = w;
 943                 this.lbase = lbase; this.lsize = lsize;
 944                 this.rbase = rbase; this.rsize = rsize;
 945                 this.wbase = wbase; this.gran = gran;
 946             }
 947 
 948             public final void compute() {
 949                 double[] a = this.a, w = this.w; // localize all params
 950                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
 951                     rn = this.rsize, k = this.wbase, g = this.gran;
 952                 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
 953                     throw new IllegalStateException(); // hoist checks
 954                 for (int lh, rh;;) {  // split larger, find point in smaller
 955                     if (ln >= rn) {
 956                         if (ln <= g)
 957                             break;
 958                         rh = rn;
 959                         double split = a[(lh = ln >>> 1) + lb];
 960                         for (int lo = 0; lo < rh; ) {
 961                             int rm = (lo + rh) >>> 1;
 962                             if (split <= a[rm + rb])
 963                                 rh = rm;
 964                             else
 965                                 lo = rm + 1;
 966                         }
 967                     }
 968                     else {
 969                         if (rn <= g)
 970                             break;
 971                         lh = ln;
 972                         double split = a[(rh = rn >>> 1) + rb];
 973                         for (int lo = 0; lo < lh; ) {
 974                             int lm = (lo + lh) >>> 1;
 975                             if (split <= a[lm + lb])
 976                                 lh = lm;
 977                             else
 978                                 lo = lm + 1;
 979                         }
 980                     }
 981                     Merger m = new Merger(this, a, w, lb + lh, ln - lh,
 982                                           rb + rh, rn - rh,
 983                                           k + lh + rh, g);
 984                     rn = rh;
 985                     ln = lh;
 986                     addToPendingCount(1);
 987                     m.fork();
 988                 }
 989 
 990                 int lf = lb + ln, rf = rb + rn; // index bounds
 991                 while (lb < lf && rb < rf) {
 992                     double t, al, ar;
 993                     if ((al = a[lb]) <= (ar = a[rb])) {
 994                         lb++; t = al;
 995                     }
 996                     else {
 997                         rb++; t = ar;
 998                     }
 999                     w[k++] = t;
1000                 }
1001                 if (rb < rf)
1002                     System.arraycopy(a, rb, w, k, rf - rb);
1003                 else if (lb < lf)
1004                     System.arraycopy(a, lb, w, k, lf - lb);
1005                 tryComplete();
1006             }
1007         }
1008     } // FJDouble
1009 
1010 }