Arrays


1   /*
2    * @(#)Arrays.java  1.59 04/04/01
3    *
4    * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   package java.util;
9   
10  import java.lang.reflect.*;
11  
12  /**
13   * This class contains various methods for manipulating arrays (such as
14   * sorting and searching).  This class also contains a static factory 
15   * that allows arrays to be viewed as lists.
16   *
17   * <p>The methods in this class all throw a <tt>NullPointerException</tt> if
18   * the specified array reference is null, except where noted.
19   *
20   * <p>The documentation for the methods contained in this class includes
21   * briefs description of the <i>implementations</i>.  Such descriptions should
22   * be regarded as <i>implementation notes</i>, rather than parts of the
23   * <i>specification</i>.  Implementors should feel free to substitute other
24   * algorithms, so long as the specification itself is adhered to.  (For
25   * example, the algorithm used by <tt>sort(Object[])</tt> does not have to be
26   * a mergesort, but it does have to be <i>stable</i>.)
27   *
28   * <p>This class is a member of the 
29   * <a HREF="{@docRoot}/../guide/collections/index.html">
30   * Java Collections Framework</a>.
31   *
32   * @author  Josh Bloch
33   * @author  Neal Gafter
34   * @version 1.59, 04/01/04
35   * @see     Comparable
36   * @see     Comparator
37   * @since   1.2
38   */
39  
40  public class Arrays {
41      // Suppresses default constructor, ensuring non-instantiability.
42      private Arrays() {
43      }
44  
45      // Sorting
46  
47      /**
48       * Sorts the specified array of longs into ascending numerical order.
49       * The sorting algorithm is a tuned quicksort, adapted from Jon
50       * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
51       * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
52       * 1993).  This algorithm offers n*log(n) performance on many data sets
53       * that cause other quicksorts to degrade to quadratic performance.
54       *
55       * @param a the array to be sorted.
56       */
57      public static void sort(long[] a) {
58      sort1(a, 0, a.length);
59      }
60  
61      /**
62       * Sorts the specified range of the specified array of longs into
63       * ascending numerical order.  The range to be sorted extends from index
64       * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
65       * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
66       *
67       * <p>The sorting algorithm is a tuned quicksort, adapted from Jon
68       * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
69       * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
70       * 1993).  This algorithm offers n*log(n) performance on many data sets
71       * that cause other quicksorts to degrade to quadratic performance.
72       *
73       * @param a the array to be sorted.
74       * @param fromIndex the index of the first element (inclusive) to be
75       *        sorted.
76       * @param toIndex the index of the last element (exclusive) to be sorted.
77       * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
78       * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
79       * <tt>toIndex &gt; a.length</tt>
80       */
81      public static void sort(long[] a, int fromIndex, int toIndex) {
82          rangeCheck(a.length, fromIndex, toIndex);
83      sort1(a, fromIndex, toIndex-fromIndex);
84      }
85  
86      /**
87       * Sorts the specified array of ints into ascending numerical order.
88       * The sorting algorithm is a tuned quicksort, adapted from Jon
89       * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
90       * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
91       * 1993).  This algorithm offers n*log(n) performance on many data sets
92       * that cause other quicksorts to degrade to quadratic performance.
93       *
94       * @param a the array to be sorted.
95       */
96      public static void sort(int[] a) {
97      sort1(a, 0, a.length);
98      }
99  
100     /**
101      * Sorts the specified range of the specified array of ints into
102      * ascending numerical order.  The range to be sorted extends from index
103      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
104      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
105      *
106      * The sorting algorithm is a tuned quicksort, adapted from Jon
107      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
108      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
109      * 1993).  This algorithm offers n*log(n) performance on many data sets
110      * that cause other quicksorts to degrade to quadratic performance.
111      *
112      * @param a the array to be sorted.
113      * @param fromIndex the index of the first element (inclusive) to be
114      *        sorted.
115      * @param toIndex the index of the last element (exclusive) to be sorted.
116      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
117      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
118      *         <tt>toIndex &gt; a.length</tt>
119      */
120     public static void sort(int[] a, int fromIndex, int toIndex) {
121         rangeCheck(a.length, fromIndex, toIndex);
122     sort1(a, fromIndex, toIndex-fromIndex);
123     }
124 
125     /**
126      * Sorts the specified array of shorts into ascending numerical order.
127      * The sorting algorithm is a tuned quicksort, adapted from Jon
128      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
129      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
130      * 1993).  This algorithm offers n*log(n) performance on many data sets
131      * that cause other quicksorts to degrade to quadratic performance.
132      *
133      * @param a the array to be sorted.
134      */
135     public static void sort(short[] a) {
136     sort1(a, 0, a.length);
137     }
138 
139     /**
140      * Sorts the specified range of the specified array of shorts into
141      * ascending numerical order.  The range to be sorted extends from index
142      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
143      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
144      *
145      * The sorting algorithm is a tuned quicksort, adapted from Jon
146      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
147      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
148      * 1993).  This algorithm offers n*log(n) performance on many data sets
149      * that cause other quicksorts to degrade to quadratic performance.
150      *
151      * @param a the array to be sorted.
152      * @param fromIndex the index of the first element (inclusive) to be
153      *        sorted.
154      * @param toIndex the index of the last element (exclusive) to be sorted.
155      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
156      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
157      *         <tt>toIndex &gt; a.length</tt>
158      */
159     public static void sort(short[] a, int fromIndex, int toIndex) {
160         rangeCheck(a.length, fromIndex, toIndex);
161     sort1(a, fromIndex, toIndex-fromIndex);
162     }
163 
164     /**
165      * Sorts the specified array of chars into ascending numerical order.
166      * The sorting algorithm is a tuned quicksort, adapted from Jon
167      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
168      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
169      * 1993).  This algorithm offers n*log(n) performance on many data sets
170      * that cause other quicksorts to degrade to quadratic performance.
171      *
172      * @param a the array to be sorted.
173      */
174     public static void sort(char[] a) {
175     sort1(a, 0, a.length);
176     }
177 
178     /**
179      * Sorts the specified range of the specified array of chars into
180      * ascending numerical order.  The range to be sorted extends from index
181      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
182      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
183      *
184      * The sorting algorithm is a tuned quicksort, adapted from Jon
185      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
186      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
187      * 1993).  This algorithm offers n*log(n) performance on many data sets
188      * that cause other quicksorts to degrade to quadratic performance.
189      *
190      * @param a the array to be sorted.
191      * @param fromIndex the index of the first element (inclusive) to be
192      *        sorted.
193      * @param toIndex the index of the last element (exclusive) to be sorted.
194      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
195      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
196      *         <tt>toIndex &gt; a.length</tt>
197      */
198     public static void sort(char[] a, int fromIndex, int toIndex) {
199         rangeCheck(a.length, fromIndex, toIndex);
200     sort1(a, fromIndex, toIndex-fromIndex);
201     }
202 
203     /**
204      * Sorts the specified array of bytes into ascending numerical order.
205      * The sorting algorithm is a tuned quicksort, adapted from Jon
206      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
207      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
208      * 1993).  This algorithm offers n*log(n) performance on many data sets
209      * that cause other quicksorts to degrade to quadratic performance.
210      *
211      * @param a the array to be sorted.
212      */
213     public static void sort(byte[] a) {
214     sort1(a, 0, a.length);
215     }
216 
217     /**
218      * Sorts the specified range of the specified array of bytes into
219      * ascending numerical order.  The range to be sorted extends from index
220      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
221      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
222      *
223      * The sorting algorithm is a tuned quicksort, adapted from Jon
224      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
225      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
226      * 1993).  This algorithm offers n*log(n) performance on many data sets
227      * that cause other quicksorts to degrade to quadratic performance.
228      *
229      * @param a the array to be sorted.
230      * @param fromIndex the index of the first element (inclusive) to be
231      *        sorted.
232      * @param toIndex the index of the last element (exclusive) to be sorted.
233      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
234      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
235      *         <tt>toIndex &gt; a.length</tt>
236      */
237     public static void sort(byte[] a, int fromIndex, int toIndex) {
238         rangeCheck(a.length, fromIndex, toIndex);
239     sort1(a, fromIndex, toIndex-fromIndex);
240     }
241 
242     /**
243      * Sorts the specified array of doubles into ascending numerical order.
244      * <p>
245      * The <code>&lt;</code> relation does not provide a total order on
246      * all floating-point values; although they are distinct numbers
247      * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
248      * compares neither less than, greater than, nor equal to any
249      * floating-point value, even itself.  To allow the sort to
250      * proceed, instead of using the <code>&lt;</code> relation to
251      * determine ascending numerical order, this method uses the total
252      * order imposed by {@link Double#compareTo}.  This ordering
253      * differs from the <code>&lt;</code> relation in that
254      * <code>-0.0</code> is treated as less than <code>0.0</code> and
255      * NaN is considered greater than any other floating-point value.
256      * For the purposes of sorting, all NaN values are considered
257      * equivalent and equal.
258      * <p>
259      * The sorting algorithm is a tuned quicksort, adapted from Jon
260      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
261      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
262      * 1993).  This algorithm offers n*log(n) performance on many data sets
263      * that cause other quicksorts to degrade to quadratic performance.
264      *
265      * @param a the array to be sorted.
266      */
267     public static void sort(double[] a) {
268     sort2(a, 0, a.length);
269     }
270 
271     /**
272      * Sorts the specified range of the specified array of doubles into
273      * ascending numerical order.  The range to be sorted extends from index
274      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
275      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
276      * <p>
277      * The <code>&lt;</code> relation does not provide a total order on
278      * all floating-point values; although they are distinct numbers
279      * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
280      * compares neither less than, greater than, nor equal to any
281      * floating-point value, even itself.  To allow the sort to
282      * proceed, instead of using the <code>&lt;</code> relation to
283      * determine ascending numerical order, this method uses the total
284      * order imposed by {@link Double#compareTo}.  This ordering
285      * differs from the <code>&lt;</code> relation in that
286      * <code>-0.0</code> is treated as less than <code>0.0</code> and
287      * NaN is considered greater than any other floating-point value.
288      * For the purposes of sorting, all NaN values are considered
289      * equivalent and equal.
290      * <p>
291      * The sorting algorithm is a tuned quicksort, adapted from Jon
292      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
293      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
294      * 1993).  This algorithm offers n*log(n) performance on many data sets
295      * that cause other quicksorts to degrade to quadratic performance.
296      *
297      * @param a the array to be sorted.
298      * @param fromIndex the index of the first element (inclusive) to be
299      *        sorted.
300      * @param toIndex the index of the last element (exclusive) to be sorted.
301      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
302      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
303      *         <tt>toIndex &gt; a.length</tt>
304      */
305     public static void sort(double[] a, int fromIndex, int toIndex) {
306         rangeCheck(a.length, fromIndex, toIndex);
307     sort2(a, fromIndex, toIndex);
308     }
309 
310     /**
311      * Sorts the specified array of floats into ascending numerical order.
312      * <p>
313      * The <code>&lt;</code> relation does not provide a total order on
314      * all floating-point values; although they are distinct numbers
315      * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
316      * compares neither less than, greater than, nor equal to any
317      * floating-point value, even itself.  To allow the sort to
318      * proceed, instead of using the <code>&lt;</code> relation to
319      * determine ascending numerical order, this method uses the total
320      * order imposed by {@link Float#compareTo}.  This ordering
321      * differs from the <code>&lt;</code> relation in that
322      * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
323      * NaN is considered greater than any other floating-point value.
324      * For the purposes of sorting, all NaN values are considered
325      * equivalent and equal.
326      * <p>
327      * The sorting algorithm is a tuned quicksort, adapted from Jon
328      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
329      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
330      * 1993).  This algorithm offers n*log(n) performance on many data sets
331      * that cause other quicksorts to degrade to quadratic performance.
332      *
333      * @param a the array to be sorted.
334      */
335     public static void sort(float[] a) {
336     sort2(a, 0, a.length);
337     }
338 
339     /**
340      * Sorts the specified range of the specified array of floats into
341      * ascending numerical order.  The range to be sorted extends from index
342      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
343      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
344      * <p>
345      * The <code>&lt;</code> relation does not provide a total order on
346      * all floating-point values; although they are distinct numbers
347      * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
348      * compares neither less than, greater than, nor equal to any
349      * floating-point value, even itself.  To allow the sort to
350      * proceed, instead of using the <code>&lt;</code> relation to
351      * determine ascending numerical order, this method uses the total
352      * order imposed by {@link Float#compareTo}.  This ordering
353      * differs from the <code>&lt;</code> relation in that
354      * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
355      * NaN is considered greater than any other floating-point value.
356      * For the purposes of sorting, all NaN values are considered
357      * equivalent and equal.
358      * <p>
359      * The sorting algorithm is a tuned quicksort, adapted from Jon
360      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
361      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
362      * 1993).  This algorithm offers n*log(n) performance on many data sets
363      * that cause other quicksorts to degrade to quadratic performance.
364      *
365      * @param a the array to be sorted.
366      * @param fromIndex the index of the first element (inclusive) to be
367      *        sorted.
368      * @param toIndex the index of the last element (exclusive) to be sorted.
369      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
370      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
371      *         <tt>toIndex &gt; a.length</tt>
372      */
373     public static void sort(float[] a, int fromIndex, int toIndex) {
374         rangeCheck(a.length, fromIndex, toIndex);
375     sort2(a, fromIndex, toIndex);
376     }
377 
378     private static void sort2(double a[], int fromIndex, int toIndex) {
379         final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
380         /*
381          * The sort is done in three phases to avoid the expense of using
382          * NaN and -0.0 aware comparisons during the main sort.
383          */
384 
385         /*
386          * Preprocessing phase:  Move any NaN's to end of array, count the
387          * number of -0.0's, and turn them into 0.0's. 
388          */
389         int numNegZeros = 0;
390         int i = fromIndex, n = toIndex;
391         while(i < n) {
392             if (a[i] != a[i]) {
393         double swap = a[i];
394                 a[i] = a[--n];
395                 a[n] = swap;
396             } else {
397                 if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) {
398                     a[i] = 0.0d;
399                     numNegZeros++;
400                 }
401                 i++;
402             }
403         }
404 
405         // Main sort phase: quicksort everything but the NaN's
406     sort1(a, fromIndex, n-fromIndex);
407 
408         // Postprocessing phase: change 0.0's to -0.0's as required
409         if (numNegZeros != 0) {
410             int j = binarySearch(a, 0.0d, fromIndex, n-1); // posn of ANY zero
411             do {
412                 j--;
413             } while (j>=0 && a[j]==0.0d);
414 
415             // j is now one less than the index of the FIRST zero
416             for (int k=0; k<numNegZeros; k++)
417                 a[++j] = -0.0d;
418         }
419     }
420 
421 
422     private static void sort2(float a[], int fromIndex, int toIndex) {
423         final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
424         /*
425          * The sort is done in three phases to avoid the expense of using
426          * NaN and -0.0 aware comparisons during the main sort.
427          */
428 
429         /*
430          * Preprocessing phase:  Move any NaN's to end of array, count the
431          * number of -0.0's, and turn them into 0.0's. 
432          */
433         int numNegZeros = 0;
434         int i = fromIndex, n = toIndex;
435         while(i < n) {
436             if (a[i] != a[i]) {
437         float swap = a[i];
438                 a[i] = a[--n];
439                 a[n] = swap;
440             } else {
441                 if (a[i]==0 && Float.floatToIntBits(a[i])==NEG_ZERO_BITS) {
442                     a[i] = 0.0f;
443                     numNegZeros++;
444                 }
445                 i++;
446             }
447         }
448 
449         // Main sort phase: quicksort everything but the NaN's
450     sort1(a, fromIndex, n-fromIndex);
451 
452         // Postprocessing phase: change 0.0's to -0.0's as required
453         if (numNegZeros != 0) {
454             int j = binarySearch(a, 0.0f, fromIndex, n-1); // posn of ANY zero
455             do {
456                 j--;
457             } while (j>=0 && a[j]==0.0f);
458 
459             // j is now one less than the index of the FIRST zero
460             for (int k=0; k<numNegZeros; k++)
461                 a[++j] = -0.0f;
462         }
463     }
464 
465 
466     /*
467      * The code for each of the seven primitive types is largely identical.
468      * C'est la vie.
469      */
470 
471     /**
472      * Sorts the specified sub-array of longs into ascending order.
473      */
474     private static void sort1(long x[], int off, int len) {
475     // Insertion sort on smallest arrays
476     if (len < 7) {
477         for (int i=off; i<len+off; i++)
478         for (int j=i; j>off && x[j-1]>x[j]; j--)
479             swap(x, j, j-1);
480         return;
481     }
482 
483     // Choose a partition element, v
484     int m = off + (len >> 1);       // Small arrays, middle element
485     if (len > 7) {
486         int l = off;
487         int n = off + len - 1;
488         if (len > 40) {        // Big arrays, pseudomedian of 9
489         int s = len/8;
490         l = med3(x, l,     l+s, l+2*s);
491         m = med3(x, m-s,   m,   m+s);
492         n = med3(x, n-2*s, n-s, n);
493         }
494         m = med3(x, l, m, n); // Mid-size, med of 3
495     }
496     long v = x[m];
497 
498     // Establish Invariant: v* (<v)* (>v)* v*
499     int a = off, b = a, c = off + len - 1, d = c;
500     while(true) {
501         while (b <= c && x[b] <= v) {
502         if (x[b] == v)
503             swap(x, a++, b);
504         b++;
505         }
506         while (c >= b && x[c] >= v) {
507         if (x[c] == v)
508             swap(x, c, d--);
509         c--;
510         }
511         if (b > c)
512         break;
513         swap(x, b++, c--);
514     }
515 
516     // Swap partition elements back to middle
517     int s, n = off + len;
518     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
519     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
520 
521     // Recursively sort non-partition-elements
522     if ((s = b-a) > 1)
523         sort1(x, off, s);
524     if ((s = d-c) > 1)
525         sort1(x, n-s, s);
526     }
527 
528     /**
529      * Swaps x[a] with x[b].
530      */
531     private static void swap(long x[], int a, int b) {
532     long t = x[a];
533     x[a] = x[b];
534     x[b] = t;
535     }
536 
537     /**
538      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
539      */
540     private static void vecswap(long x[], int a, int b, int n) {
541     for (int i=0; i<n; i++, a++, b++)
542         swap(x, a, b);
543     }
544 
545     /**
546      * Returns the index of the median of the three indexed longs.
547      */
548     private static int med3(long x[], int a, int b, int c) {
549     return (x[a] < x[b] ?
550         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
551         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
552     }
553 
554     /**
555      * Sorts the specified sub-array of integers into ascending order.
556      */
557     private static void sort1(int x[], int off, int len) {
558     // Insertion sort on smallest arrays
559     if (len < 7) {
560         for (int i=off; i<len+off; i++)
561         for (int j=i; j>off && x[j-1]>x[j]; j--)
562             swap(x, j, j-1);
563         return;
564     }
565 
566     // Choose a partition element, v
567     int m = off + (len >> 1);       // Small arrays, middle element
568     if (len > 7) {
569         int l = off;
570         int n = off + len - 1;
571         if (len > 40) {        // Big arrays, pseudomedian of 9
572         int s = len/8;
573         l = med3(x, l,     l+s, l+2*s);
574         m = med3(x, m-s,   m,   m+s);
575         n = med3(x, n-2*s, n-s, n);
576         }
577         m = med3(x, l, m, n); // Mid-size, med of 3
578     }
579     int v = x[m];
580 
581     // Establish Invariant: v* (<v)* (>v)* v*
582     int a = off, b = a, c = off + len - 1, d = c;
583     while(true) {
584         while (b <= c && x[b] <= v) {
585         if (x[b] == v)
586             swap(x, a++, b);
587         b++;
588         }
589         while (c >= b && x[c] >= v) {
590         if (x[c] == v)
591             swap(x, c, d--);
592         c--;
593         }
594         if (b > c)
595         break;
596         swap(x, b++, c--);
597     }
598 
599     // Swap partition elements back to middle
600     int s, n = off + len;
601     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
602     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
603 
604     // Recursively sort non-partition-elements
605     if ((s = b-a) > 1)
606         sort1(x, off, s);
607     if ((s = d-c) > 1)
608         sort1(x, n-s, s);
609     }
610 
611     /**
612      * Swaps x[a] with x[b].
613      */
614     private static void swap(int x[], int a, int b) {
615     int t = x[a];
616     x[a] = x[b];
617     x[b] = t;
618     }
619 
620     /**
621      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
622      */
623     private static void vecswap(int x[], int a, int b, int n) {
624     for (int i=0; i<n; i++, a++, b++)
625         swap(x, a, b);
626     }
627 
628     /**
629      * Returns the index of the median of the three indexed integers.
630      */
631     private static int med3(int x[], int a, int b, int c) {
632     return (x[a] < x[b] ?
633         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
634         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
635     }
636 
637     /**
638      * Sorts the specified sub-array of shorts into ascending order.
639      */
640     private static void sort1(short x[], int off, int len) {
641     // Insertion sort on smallest arrays
642     if (len < 7) {
643         for (int i=off; i<len+off; i++)
644         for (int j=i; j>off && x[j-1]>x[j]; j--)
645             swap(x, j, j-1);
646         return;
647     }
648 
649     // Choose a partition element, v
650     int m = off + (len >> 1);       // Small arrays, middle element
651     if (len > 7) {
652         int l = off;
653         int n = off + len - 1;
654         if (len > 40) {        // Big arrays, pseudomedian of 9
655         int s = len/8;
656         l = med3(x, l,     l+s, l+2*s);
657         m = med3(x, m-s,   m,   m+s);
658         n = med3(x, n-2*s, n-s, n);
659         }
660         m = med3(x, l, m, n); // Mid-size, med of 3
661     }
662     short v = x[m];
663 
664     // Establish Invariant: v* (<v)* (>v)* v*
665     int a = off, b = a, c = off + len - 1, d = c;
666     while(true) {
667         while (b <= c && x[b] <= v) {
668         if (x[b] == v)
669             swap(x, a++, b);
670         b++;
671         }
672         while (c >= b && x[c] >= v) {
673         if (x[c] == v)
674             swap(x, c, d--);
675         c--;
676         }
677         if (b > c)
678         break;
679         swap(x, b++, c--);
680     }
681 
682     // Swap partition elements back to middle
683     int s, n = off + len;
684     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
685     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
686 
687     // Recursively sort non-partition-elements
688     if ((s = b-a) > 1)
689         sort1(x, off, s);
690     if ((s = d-c) > 1)
691         sort1(x, n-s, s);
692     }
693 
694     /**
695      * Swaps x[a] with x[b].
696      */
697     private static void swap(short x[], int a, int b) {
698     short t = x[a];
699     x[a] = x[b];
700     x[b] = t;
701     }
702 
703     /**
704      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
705      */
706     private static void vecswap(short x[], int a, int b, int n) {
707     for (int i=0; i<n; i++, a++, b++)
708         swap(x, a, b);
709     }
710 
711     /**
712      * Returns the index of the median of the three indexed shorts.
713      */
714     private static int med3(short x[], int a, int b, int c) {
715     return (x[a] < x[b] ?
716         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
717         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
718     }
719 
720 
721     /**
722      * Sorts the specified sub-array of chars into ascending order.
723      */
724     private static void sort1(char x[], int off, int len) {
725     // Insertion sort on smallest arrays
726     if (len < 7) {
727         for (int i=off; i<len+off; i++)
728         for (int j=i; j>off && x[j-1]>x[j]; j--)
729             swap(x, j, j-1);
730         return;
731     }
732 
733     // Choose a partition element, v
734     int m = off + (len >> 1);       // Small arrays, middle element
735     if (len > 7) {
736         int l = off;
737         int n = off + len - 1;
738         if (len > 40) {        // Big arrays, pseudomedian of 9
739         int s = len/8;
740         l = med3(x, l,     l+s, l+2*s);
741         m = med3(x, m-s,   m,   m+s);
742         n = med3(x, n-2*s, n-s, n);
743         }
744         m = med3(x, l, m, n); // Mid-size, med of 3
745     }
746     char v = x[m];
747 
748     // Establish Invariant: v* (<v)* (>v)* v*
749     int a = off, b = a, c = off + len - 1, d = c;
750     while(true) {
751         while (b <= c && x[b] <= v) {
752         if (x[b] == v)
753             swap(x, a++, b);
754         b++;
755         }
756         while (c >= b && x[c] >= v) {
757         if (x[c] == v)
758             swap(x, c, d--);
759         c--;
760         }
761         if (b > c)
762         break;
763         swap(x, b++, c--);
764     }
765 
766     // Swap partition elements back to middle
767     int s, n = off + len;
768     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
769     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
770 
771     // Recursively sort non-partition-elements
772     if ((s = b-a) > 1)
773         sort1(x, off, s);
774     if ((s = d-c) > 1)
775         sort1(x, n-s, s);
776     }
777 
778     /**
779      * Swaps x[a] with x[b].
780      */
781     private static void swap(char x[], int a, int b) {
782     char t = x[a];
783     x[a] = x[b];
784     x[b] = t;
785     }
786 
787     /**
788      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
789      */
790     private static void vecswap(char x[], int a, int b, int n) {
791     for (int i=0; i<n; i++, a++, b++)
792         swap(x, a, b);
793     }
794 
795     /**
796      * Returns the index of the median of the three indexed chars.
797      */
798     private static int med3(char x[], int a, int b, int c) {
799     return (x[a] < x[b] ?
800         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
801         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
802     }
803 
804 
805     /**
806      * Sorts the specified sub-array of bytes into ascending order.
807      */
808     private static void sort1(byte x[], int off, int len) {
809     // Insertion sort on smallest arrays
810     if (len < 7) {
811         for (int i=off; i<len+off; i++)
812         for (int j=i; j>off && x[j-1]>x[j]; j--)
813             swap(x, j, j-1);
814         return;
815     }
816 
817     // Choose a partition element, v
818     int m = off + (len >> 1);       // Small arrays, middle element
819     if (len > 7) {
820         int l = off;
821         int n = off + len - 1;
822         if (len > 40) {        // Big arrays, pseudomedian of 9
823         int s = len/8;
824         l = med3(x, l,     l+s, l+2*s);
825         m = med3(x, m-s,   m,   m+s);
826         n = med3(x, n-2*s, n-s, n);
827         }
828         m = med3(x, l, m, n); // Mid-size, med of 3
829     }
830     byte v = x[m];
831 
832     // Establish Invariant: v* (<v)* (>v)* v*
833     int a = off, b = a, c = off + len - 1, d = c;
834     while(true) {
835         while (b <= c && x[b] <= v) {
836         if (x[b] == v)
837             swap(x, a++, b);
838         b++;
839         }
840         while (c >= b && x[c] >= v) {
841         if (x[c] == v)
842             swap(x, c, d--);
843         c--;
844         }
845         if (b > c)
846         break;
847         swap(x, b++, c--);
848     }
849 
850     // Swap partition elements back to middle
851     int s, n = off + len;
852     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
853     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
854 
855     // Recursively sort non-partition-elements
856     if ((s = b-a) > 1)
857         sort1(x, off, s);
858     if ((s = d-c) > 1)
859         sort1(x, n-s, s);
860     }
861 
862     /**
863      * Swaps x[a] with x[b].
864      */
865     private static void swap(byte x[], int a, int b) {
866     byte t = x[a];
867     x[a] = x[b];
868     x[b] = t;
869     }
870 
871     /**
872      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
873      */
874     private static void vecswap(byte x[], int a, int b, int n) {
875     for (int i=0; i<n; i++, a++, b++)
876         swap(x, a, b);
877     }
878 
879     /**
880      * Returns the index of the median of the three indexed bytes.
881      */
882     private static int med3(byte x[], int a, int b, int c) {
883     return (x[a] < x[b] ?
884         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
885         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
886     }
887 
888 
889     /**
890      * Sorts the specified sub-array of doubles into ascending order.
891      */
892     private static void sort1(double x[], int off, int len) {
893     // Insertion sort on smallest arrays
894     if (len < 7) {
895         for (int i=off; i<len+off; i++)
896         for (int j=i; j>off && x[j-1]>x[j]; j--)
897             swap(x, j, j-1);
898         return;
899     }
900 
901     // Choose a partition element, v
902     int m = off + (len >> 1);       // Small arrays, middle element
903     if (len > 7) {
904         int l = off;
905         int n = off + len - 1;
906         if (len > 40) {        // Big arrays, pseudomedian of 9
907         int s = len/8;
908         l = med3(x, l,     l+s, l+2*s);
909         m = med3(x, m-s,   m,   m+s);
910         n = med3(x, n-2*s, n-s, n);
911         }
912         m = med3(x, l, m, n); // Mid-size, med of 3
913     }
914     double v = x[m];
915 
916     // Establish Invariant: v* (<v)* (>v)* v*
917     int a = off, b = a, c = off + len - 1, d = c;
918     while(true) {
919         while (b <= c && x[b] <= v) {
920         if (x[b] == v)
921             swap(x, a++, b);
922         b++;
923         }
924         while (c >= b && x[c] >= v) {
925         if (x[c] == v)
926             swap(x, c, d--);
927         c--;
928         }
929         if (b > c)
930         break;
931         swap(x, b++, c--);
932     }
933 
934     // Swap partition elements back to middle
935     int s, n = off + len;
936     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
937     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
938 
939     // Recursively sort non-partition-elements
940     if ((s = b-a) > 1)
941         sort1(x, off, s);
942     if ((s = d-c) > 1)
943         sort1(x, n-s, s);
944     }
945 
946     /**
947      * Swaps x[a] with x[b].
948      */
949     private static void swap(double x[], int a, int b) {
950     double t = x[a];
951     x[a] = x[b];
952     x[b] = t;
953     }
954 
955     /**
956      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
957      */
958     private static void vecswap(double x[], int a, int b, int n) {
959     for (int i=0; i<n; i++, a++, b++)
960         swap(x, a, b);
961     }
962 
963     /**
964      * Returns the index of the median of the three indexed doubles.
965      */
966     private static int med3(double x[], int a, int b, int c) {
967     return (x[a] < x[b] ?
968         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
969         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
970     }
971 
972 
973     /**
974      * Sorts the specified sub-array of floats into ascending order.
975      */
976     private static void sort1(float x[], int off, int len) {
977     // Insertion sort on smallest arrays
978     if (len < 7) {
979         for (int i=off; i<len+off; i++)
980         for (int j=i; j>off && x[j-1]>x[j]; j--)
981             swap(x, j, j-1);
982         return;
983     }
984 
985     // Choose a partition element, v
986     int m = off + (len >> 1);       // Small arrays, middle element
987     if (len > 7) {
988         int l = off;
989         int n = off + len - 1;
990         if (len > 40) {        // Big arrays, pseudomedian of 9
991         int s = len/8;
992         l = med3(x, l,     l+s, l+2*s);
993         m = med3(x, m-s,   m,   m+s);
994         n = med3(x, n-2*s, n-s, n);
995         }
996         m = med3(x, l, m, n); // Mid-size, med of 3
997     }
998     float v = x[m];
999 
1000    // Establish Invariant: v* (<v)* (>v)* v*
1001    int a = off, b = a, c = off + len - 1, d = c;
1002    while(true) {
1003        while (b <= c && x[b] <= v) {
1004