View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  package org.apache.commons.numbers.examples.jmh.arrays;
19  
20  /**
21   * A strategy to pick two pivot indices of an array for partitioning.
22   *
23   * <p>An ideal strategy will pick the tertiles across a variety of data so
24   * to divide the data into [1/3, 1/3, 1/3].
25   *
26   * @see <a href="https://en.wiktionary.org/wiki/tertile">Tertile (Wiktionary)</a>
27   * @since 1.2
28   */
29  enum DualPivotingStrategy {
30      /**
31       * Pivot around the medians at 1/3 and 2/3 of the range.
32       *
33       * <p>Requires {@code right - left >= 2}.
34       *
35       * <p>On sorted data the tertiles are: 0.3340 0.6670
36       * <p>On random data the tertiles are:
37       * <pre>
38       *         min      max     mean       sd   median     skew
39       * [1]  0.0000   0.9970   0.3327   0.2357   0.2920   0.5654
40       * [2]  0.0020   1.0000   0.3346   0.2356   0.2940   0.5675
41       * [3]  0.0000   0.9970   0.3328   0.2356   0.2920   0.5656
42       * </pre>
43       */
44      MEDIANS {
45          @Override
46          int pivotIndex(double[] data, int left, int right, int[] pivot2) {
47              // Original 'medians' method from the dual-pivot quicksort paper by Vladimir Yaroslavskiy
48              final int len = right - left;
49              // Do not pivot at the ends by setting 1/3 to at least 1.
50              // This is safe if len >= 2.
51              final int third = Math.max(1, len / 3);
52              final int m1 = left + third;
53              final int m2 = right - third;
54              // Ensure p1 is lower
55              if (data[m1] < data[m2]) {
56                  pivot2[0] = m2;
57                  return m1;
58              }
59              pivot2[0] = m1;
60              return m2;
61          }
62  
63          @Override
64          int[] getSampledIndices(int left, int right) {
65              final int len = right - left;
66              final int third = Math.max(1, len / 3);
67              final int m1 = left + third;
68              final int m2 = right - third;
69              return new int[] {m1, m2};
70          }
71  
72          @Override
73          int samplingEffect() {
74              return UNCHANGED;
75          }
76      },
77      /**
78       * Pivot around the 2nd and 4th values from 5 approximately uniformly spaced within the range.
79       * Uses points +/- sixths from the median: 1/6, 1/3, 1/2, 2/3, 5/6.
80       *
81       * <p>Requires {@code right - left >= 4}.
82       *
83       * <p>Warning: This has the side effect that the 5 values are also sorted.
84       *
85       * <p>On sorted data the tertiles are: 0.3290 0.6710
86       * <p>On random data the tertiles are:
87       * <pre>
88       *         min      max     mean       sd   median     skew
89       * [1]  0.0010   0.9820   0.3327   0.1778   0.3130   0.4650
90       * [2]  0.0030   0.9760   0.3348   0.1778   0.3150   0.4665
91       * [3]  0.0010   0.9870   0.3325   0.1779   0.3130   0.4698
92       * </pre>
93       */
94      SORT_5 {
95          @Override
96          int pivotIndex(double[] data, int left, int right, int[] pivot2) {
97              // 1/6 = 5/30 ~ 1/8 + 1/32 + 1/64 : 0.1666 ~ 0.1719
98              // Ensure the value is above zero to choose different points!
99              // This is safe if len >= 4.
100             final int len = right - left;
101             final int sixth = 1 + (len >>> 3) + (len >>> 5) + (len >>> 6);
102             final int p3 = left + (len >>> 1);
103             final int p2 = p3 - sixth;
104             final int p1 = p2 - sixth;
105             final int p4 = p3 + sixth;
106             final int p5 = p4 + sixth;
107             Sorting.sort5(data, p1, p2, p3, p4, p5);
108             pivot2[0] = p4;
109             return p2;
110         }
111 
112         @Override
113         int[] getSampledIndices(int left, int right) {
114             final int len = right - left;
115             final int sixth = 1 + (len >>> 3) + (len >>> 5) + (len >>> 6);
116             final int p3 = left + (len >>> 1);
117             final int p2 = p3 - sixth;
118             final int p1 = p2 - sixth;
119             final int p4 = p3 + sixth;
120             final int p5 = p4 + sixth;
121             return new int[] {p1, p2, p3, p4, p5};
122         }
123 
124         @Override
125         int samplingEffect() {
126             return SORT;
127         }
128     },
129     /**
130      * Pivot around the 2nd and 4th values from 5 approximately uniformly spaced within the range.
131      * Uses points +/- sevenths from the median: 3/14, 5/14, 1/2, 9/14, 11/14.
132      *
133      * <p>Requires {@code right - left >= 4}.
134      *
135      * <p>Warning: This has the side effect that the 5 values are also sorted.
136      *
137      * <p>On sorted data the tertiles are: 0.3600 0.6400
138      * <p>On random data the tertiles are:
139      * <pre>
140      *         min      max     mean       sd   median     skew
141      * [1]  0.0010   0.9790   0.3330   0.1780   0.3140   0.4665
142      * [2]  0.0030   0.9800   0.3348   0.1778   0.3150   0.4681
143      * [3]  0.0010   0.9770   0.3322   0.1777   0.3130   0.4677
144      * </pre>
145      */
146     SORT_5B {
147         @Override
148         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
149             // 1/7 = 5/35 ~ 1/8 + 1/64 : 0.1429 ~ 0.1406
150             // Ensure the value is above zero to choose different points!
151             // This is safe if len >= 4.
152             final int len = right - left;
153             final int seventh = 1 + (len >>> 3) + (len >>> 6);
154             final int p3 = left + (len >>> 1);
155             final int p2 = p3 - seventh;
156             final int p1 = p2 - seventh;
157             final int p4 = p3 + seventh;
158             final int p5 = p4 + seventh;
159             Sorting.sort5(data, p1, p2, p3, p4, p5);
160             pivot2[0] = p4;
161             return p2;
162         }
163 
164         @Override
165         int[] getSampledIndices(int left, int right) {
166             final int len = right - left;
167             final int seventh = 1 + (len >>> 3) + (len >>> 6);
168             final int p3 = left + (len >>> 1);
169             final int p2 = p3 - seventh;
170             final int p1 = p2 - seventh;
171             final int p4 = p3 + seventh;
172             final int p5 = p4 + seventh;
173             return new int[] {p1, p2, p3, p4, p5};
174         }
175 
176         @Override
177         int samplingEffect() {
178             return SORT;
179         }
180     },
181     /**
182      * This strategy is the same as {@link #SORT_5B} with the exception that it
183      * returns identical pivots if the data at the chosen pivots is equal.
184      *
185      * <p>This allows testing switching to a single pivot strategy against using
186      * a dual pivot partitioning with effectively only 1 pivot. This requires
187      * the dual pivot partition function to check pivot1 == pivot2. If the
188      * dual pivot partition function checks data[pivot1] == data[pivot2] then
189      * the switching choice cannot be enabled/disabled by changing pivoting strategy
190      * and must use another mechanism.
191      *
192      * <p>This specific strategy has been selected for single-pivot switching as
193      * {@link #SORT_5B} benchmarks as consistently fast across all data input.
194      */
195     SORT_5B_SP {
196         @Override
197         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
198             final int pivot1 = SORT_5B.pivotIndex(data, left, right, pivot2);
199             if (data[pivot1] == data[pivot2[0]]) {
200                 // Here 3 of 5 middle values are the same.
201                 // Present single-pivot pivot methods would not
202                 // have an advantage pivoting on p2, p3, or p4; just use 'p2'
203                 pivot2[0] = pivot1;
204             }
205             return pivot1;
206         }
207 
208         @Override
209         int[] getSampledIndices(int left, int right) {
210             return SORT_5B.getSampledIndices(left, right);
211         }
212 
213         @Override
214         int samplingEffect() {
215             return SORT;
216         }
217     },
218     /**
219      * Pivot around the 2nd and 4th values from 5 approximately uniformly spaced within the range.
220      * Uses points +/- eights from the median: 1/4, 3/8, 1/2, 5/8, 3/4.
221      *
222      * <p>Requires {@code right - left >= 4}.
223      *
224      * <p>Warning: This has the side effect that the 5 values are also sorted.
225      *
226      * <p>On sorted data the tertiles are: 0.3750 0.6250
227      * <p>On random data the tertiles are:
228      * <pre>
229      *         min      max     mean       sd   median     skew
230      * [1]  0.0010   0.9790   0.3324   0.1779   0.3130   0.4666
231      * [2]  0.0030   0.9850   0.3348   0.1778   0.3150   0.4686
232      * [3]  0.0010   0.9720   0.3327   0.1779   0.3130   0.4666
233      * </pre>
234      */
235     SORT_5C {
236         @Override
237         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
238             // 1/8 = 0.125
239             // Ensure the value is above zero to choose different points!
240             // This is safe if len >= 4.
241             final int len = right - left;
242             final int eighth = 1 + (len >>> 3);
243             final int p3 = left + (len >>> 1);
244             final int p2 = p3 - eighth;
245             final int p1 = p2 - eighth;
246             final int p4 = p3 + eighth;
247             final int p5 = p4 + eighth;
248             Sorting.sort5(data, p1, p2, p3, p4, p5);
249             pivot2[0] = p4;
250             return p2;
251         }
252 
253         @Override
254         int[] getSampledIndices(int left, int right) {
255             final int len = right - left;
256             final int eighth = 1 + (len >>> 3);
257             final int p3 = left + (len >>> 1);
258             final int p2 = p3 - eighth;
259             final int p1 = p2 - eighth;
260             final int p4 = p3 + eighth;
261             final int p5 = p4 + eighth;
262             return new int[] {p1, p2, p3, p4, p5};
263         }
264 
265         @Override
266         int samplingEffect() {
267             return SORT;
268         }
269     },
270     /**
271      * Pivot around the 2nd and 4th values from 5 medians approximately uniformly spaced within
272      * the range. The medians are from 3 samples. The 5 samples of 3 do not overlap thus this
273      * method requires {@code right - left >= 14}. The samples can be visualised as 5 sorted
274      * columns:
275      *
276      * <pre>
277      * v w x y z
278      * 1 2 3 4 5
279      * a b c d e
280      * </pre>
281      *
282      * <p>The pivots are points 2 and 4. The other points are either known to be below or
283      * above the pivots; or potentially below or above the pivots.
284      *
285      * <p>Pivot 1: below {@code 1,a,b}; potentially below {@code v,c,d,e}. This ranks
286      * pivot 1 from 4/15 to 8/15 and exactly 5/15 if the input data is sorted/reverse sorted.
287      *
288      * <p>Pivot 2: above {@code 5,y,z}; potentially above {@code e,v,w,x}. This ranks
289      * pivot 2 from 7/15 to 11/15 and exactly 10/15 if the input data is sorted/reverse sorted.
290      *
291      * <p>Warning: This has the side effect that the 15 samples values are partially sorted.
292      *
293      * <p>On sorted data the tertiles are: 0.3140 0.6860
294      * <p>On random data the tertiles are:
295      * <pre>
296      *         min      max     mean       sd   median     skew
297      * [1]  0.0090   0.9170   0.3783   0.1320   0.3730   0.2107
298      * [2]  0.0030   0.8950   0.2438   0.1328   0.2270   0.6150
299      * [3]  0.0110   0.9140   0.3779   0.1319   0.3730   0.2114
300      * </pre>
301      * <p>Note the bias towards the outer regions.
302      */
303     SORT_5_OF_3 {
304         @Override
305         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
306             // Step size of 1/16 of the length
307             final int len = right - left;
308             final int step = Math.max(1, len >>> 4);
309             final int step3 = step * 3;
310             final int p3 = left + (len >>> 1);
311             final int p2 = p3 - step3;
312             final int p1 = p2 - step3;
313             final int p4 = p3 + step3;
314             final int p5 = p4 + step3;
315             // 5 medians of 3
316             Sorting.sort3(data, p1 - step, p1, p1 + step);
317             Sorting.sort3(data, p2 - step, p2, p2 + step);
318             Sorting.sort3(data, p3 - step, p3, p3 + step);
319             Sorting.sort3(data, p4 - step, p4, p4 + step);
320             Sorting.sort3(data, p5 - step, p5, p5 + step);
321             // Sort the medians
322             Sorting.sort5(data, p1, p2, p3, p4, p5);
323             pivot2[0] = p4;
324             return p2;
325         }
326 
327         @Override
328         int[] getSampledIndices(int left, int right) {
329             final int len = right - left;
330             final int step = Math.max(1, len >>> 4);
331             final int step3 = step * 3;
332             final int p3 = left + (len >>> 1);
333             final int p2 = p3 - step3;
334             final int p1 = p2 - step3;
335             final int p4 = p3 + step3;
336             final int p5 = p4 + step3;
337             return new int[] {
338                 p1 - step, p1, p1 + step,
339                 p2 - step, p2, p2 + step,
340                 p3 - step, p3, p3 + step,
341                 p4 - step, p4, p4 + step,
342                 p5 - step, p5, p5 + step,
343             };
344         }
345 
346         @Override
347         int samplingEffect() {
348             return PARTIAL_SORT;
349         }
350     },
351     /**
352      * Pivot around the 2nd and 3rd values from 4 medians approximately uniformly spaced within
353      * the range. The medians are from 3 samples. The 4 samples of 3 do not overlap thus this
354      * method requires {@code right - left >= 11}. The samples can be visualised as 4 sorted
355      * columns:
356      *
357      * <pre>
358      * w x y z
359      * 1 2 3 4
360      * a b c d
361      * </pre>
362      *
363      * <p>The pivots are points 2 and 3. The other points are either known to be below or
364      * above the pivots; or potentially below or above the pivots.
365      *
366      * <p>Pivot 1: below {@code 1,a,b}; potentially below {@code w,c,d}. This ranks
367      * pivot 1 from 4/12 to 7/12 and exactly 5/12 if the input data is sorted/reverse sorted.
368      *
369      * <p>Pivot 2: above {@code 4,y,z}; potentially above {@code d,w,x}. This ranks
370      * pivot 2 from 5/15 to 8/12 and exactly 7/12 if the input data is sorted/reverse sorted.
371      *
372      * <p>Warning: This has the side effect that the 12 samples values are partially sorted.
373      *
374      * <p>On sorted data the tertiles are: 0.3850 0.6160
375      * <p>On random data the tertiles are:
376      * <pre>
377      *         min      max     mean       sd   median     skew
378      * [1]  0.0160   0.9580   0.4269   0.1454   0.4230   0.1366
379      * [2]  0.0020   0.8270   0.1467   0.1193   0.1170   1.1417
380      * [3]  0.0140   0.9560   0.4264   0.1453   0.4230   0.1352
381      * </pre>
382      * <p>Note the large bias towards the outer regions.
383      */
384     SORT_4_OF_3 {
385         @Override
386         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
387             // Step size of 1/13 of the length: 1/13 ~ 1/16 + 1/64 : 0.0769 ~ 0.0781
388             final int len = right - left;
389             final int step = Math.max(1, (len >>> 4) + (len >>> 6));
390             final int step3 = step * 3;
391             final int p1 = left + (step << 1) - 1;
392             final int p2 = p1 + step3;
393             final int p3 = p2 + step3;
394             final int p4 = p3 + step3;
395             // 5 medians of 3
396             Sorting.sort3(data, p1 - step, p1, p1 + step);
397             Sorting.sort3(data, p2 - step, p2, p2 + step);
398             Sorting.sort3(data, p3 - step, p3, p3 + step);
399             Sorting.sort3(data, p4 - step, p4, p4 + step);
400             // Sort the medians
401             Sorting.sort4(data, p1, p2, p3, p4);
402             pivot2[0] = p3;
403             return p2;
404         }
405 
406         @Override
407         int[] getSampledIndices(int left, int right) {
408             final int len = right - left;
409             final int step = Math.max(1, (len >>> 4) + (len >>> 6));
410             final int step3 = step * 3;
411             final int p1 = left + (step << 1) - 1;
412             final int p2 = p1 + step3;
413             final int p3 = p2 + step3;
414             final int p4 = p3 + step3;
415             return new int[] {
416                 p1 - step, p1, p1 + step,
417                 p2 - step, p2, p2 + step,
418                 p3 - step, p3, p3 + step,
419                 p4 - step, p4, p4 + step,
420             };
421         }
422 
423         @Override
424         int samplingEffect() {
425             return PARTIAL_SORT;
426         }
427     },
428     /**
429      * Pivot around the 1st and 3rd values from 3 medians approximately uniformly spaced within
430      * the range. The medians are from 3 samples. The 3 samples of 3 do not overlap thus this
431      * method requires {@code right - left >= 8}. The samples can be visualised as 3 sorted
432      * columns:
433      *
434      * <pre>
435      * x y z
436      * 1 2 3
437      * a b c
438      * </pre>
439      *
440      * <p>The pivots are points 1 and 3. The other points are either known to be below or
441      * above the pivots; or potentially below or above the pivots.
442      *
443      * <p>Pivot 1: below {@code a}; potentially below {@code b, c}. This ranks
444      * pivot 1 from 2/9 to 4/9 and exactly 2/9 if the input data is sorted/reverse sorted.
445      *
446      * <p>Pivot 2: above {@code z}; potentially above {@code x,y}. This ranks
447      * pivot 2 from 6/9 to 8/9 and exactly 8/9 if the input data is sorted/reverse sorted.
448      *
449      * <p>Warning: This has the side effect that the 9 samples values are partially sorted.
450      *
451      * <p>On sorted data the tertiles are: 0.1280 0.8720
452      * <p>On random data the tertiles are:
453      * <pre>
454      *         min      max     mean       sd   median     skew
455      * [1]  0.0010   0.9460   0.3062   0.1560   0.2910   0.4455
456      * [2]  0.0030   0.9820   0.3875   0.1813   0.3780   0.2512
457      * [3]  0.0010   0.9400   0.3063   0.1558   0.2910   0.4453
458      * </pre>
459      * <p>Note the bias towards the central region.
460      */
461     SORT_3_OF_3 {
462         @Override
463         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
464             // Step size of 1/8 of the length
465             final int len = right - left;
466             final int step = Math.max(1, len >>> 3);
467             final int step3 = step * 3;
468             final int p2 = left + (len >>> 1);
469             final int p1 = p2 - step3;
470             final int p3 = p2 + step3;
471             // 3 medians of 3
472             Sorting.sort3(data, p1 - step, p1, p1 + step);
473             Sorting.sort3(data, p2 - step, p2, p2 + step);
474             Sorting.sort3(data, p3 - step, p3, p3 + step);
475             // Sort the medians
476             Sorting.sort3(data, p1, p2, p3);
477             pivot2[0] = p3;
478             return p1;
479         }
480 
481         @Override
482         int[] getSampledIndices(int left, int right) {
483             final int len = right - left;
484             final int step = Math.max(1, len >>> 3);
485             final int step3 = step * 3;
486             final int p2 = left + (len >>> 1);
487             final int p1 = p2 - step3;
488             final int p3 = p2 + step3;
489             return new int[] {
490                 p1 - step, p1, p1 + step,
491                 p2 - step, p2, p2 + step,
492                 p3 - step, p3, p3 + step,
493             };
494         }
495 
496         @Override
497         int samplingEffect() {
498             return PARTIAL_SORT;
499         }
500     },
501     /**
502      * Pivot around the 2nd and 4th values from 5 medians approximately uniformly spaced within
503      * the range. The medians are from 5 samples. The 5 samples of 5 do not overlap thus this
504      * method requires {@code right - left >= 24}. The samples can be visualised as 5 sorted
505      * columns:
506      *
507      * <pre>
508      * v w x y z
509      * q r s t u
510      * 1 2 3 4 5
511      * f g h i j
512      * a b c d e
513      * </pre>
514      *
515      * <p>The pivots are points 2 and 4. The other points are either known to be below or
516      * above the pivots; or potentially below or above the pivots.
517      *
518      * <p>Pivot 1: below {@code 1,a,b,f,g}; potentially below {@code q,v,c,d,e,h,i,j}. This ranks
519      * pivot 1 from 6/25 to 14/25 and exactly 8/25 if the input data is sorted/reverse sorted.
520      *
521      * <p>Pivot 2 by symmetry from 12/25 to 20/25 and exactly 18/25 for sorted data.
522      *
523      * <p>Warning: This has the side effect that the 25 samples values are partially sorted.
524      *
525      * <p>On sorted data the tertiles are: 0.3050 0.6950
526      * <p>On random data the tertiles are:
527      * <pre>
528      *         min      max     mean       sd   median     skew
529      * [1]  0.0270   0.8620   0.3996   0.1093   0.3970   0.1130
530      * [2]  0.0030   0.8100   0.2010   0.1106   0.1860   0.6691
531      * [3]  0.0270   0.8970   0.3994   0.1093   0.3970   0.1147
532      * </pre>
533      * <p>Note the bias towards the outer regions on random data but the inner region on
534      * sorted data.
535      */
536     SORT_5_OF_5 {
537         @Override
538         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
539             // Step size of 1/25 of the length
540             final int len = right - left;
541             final int step = Math.max(1, len / 25);
542             final int step2 = step << 1;
543             final int step5 = step * 5;
544             final int p3 = left + (len >>> 1);
545             final int p2 = p3 - step5;
546             final int p1 = p2 - step5;
547             final int p4 = p3 + step5;
548             final int p5 = p4 + step5;
549             // 5 medians of 3
550             Sorting.sort5(data, p1 - step2, p1 - step, p1, p1 + step, p1 + step2);
551             Sorting.sort5(data, p2 - step2, p2 - step, p2, p2 + step, p2 + step2);
552             Sorting.sort5(data, p3 - step2, p3 - step, p3, p3 + step, p3 + step2);
553             Sorting.sort5(data, p4 - step2, p4 - step, p4, p4 + step, p4 + step2);
554             Sorting.sort5(data, p5 - step2, p5 - step, p5, p5 + step, p5 + step2);
555             // Sort the medians
556             Sorting.sort5(data, p1, p2, p3, p4, p5);
557             pivot2[0] = p4;
558             return p2;
559         }
560 
561         @Override
562         int[] getSampledIndices(int left, int right) {
563             // Step size of 1/25 of the length
564             final int len = right - left;
565             final int step = Math.max(1, len / 25);
566             final int step2 = step << 1;
567             final int step5 = step * 5;
568             final int p3 = left + (len >>> 1);
569             final int p2 = p3 - step5;
570             final int p1 = p2 - step5;
571             final int p4 = p3 + step5;
572             final int p5 = p4 + step5;
573             return new int[] {
574                 p1 - step2, p1 - step, p1, p1 + step, p1 + step2,
575                 p2 - step2, p2 - step, p2, p2 + step, p2 + step2,
576                 p3 - step2, p3 - step, p3, p3 + step, p3 + step2,
577                 p4 - step2, p4 - step, p4, p4 + step, p4 + step2,
578                 p5 - step2, p5 - step, p5, p5 + step, p5 + step2,
579             };
580         }
581 
582         @Override
583         int samplingEffect() {
584             return PARTIAL_SORT;
585         }
586     },
587     /**
588      * Pivot around the 3rd and 5th values from 7 approximately uniformly spaced within the range.
589      * Uses points +/- eights from the median: 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8.
590      *
591      * <p>Requires {@code right - left >= 6}.
592      *
593      * <p>Warning: This has the side effect that the 7 values are also sorted.
594      *
595      * <p>On sorted data the tertiles are: 0.3760 0.6240
596      * <p>On random data the tertiles are:
597      * <pre>
598      *         min      max     mean       sd   median     skew
599      * [1]  0.0020   0.9600   0.3745   0.1609   0.3640   0.3092
600      * [2]  0.0030   0.9490   0.2512   0.1440   0.2300   0.6920
601      * [3]  0.0030   0.9620   0.3743   0.1609   0.3640   0.3100
602      * </pre>
603      * <p>Note the bias towards the outer regions.
604      */
605     SORT_7 {
606         @Override
607         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
608             // Ensure the value is above zero to choose different points!
609             // This is safe if len >= 4.
610             final int len = right - left;
611             final int eighth = Math.max(1, len >>> 3);
612             final int p4 = left + (len >>> 1);
613             final int p3 = p4 - eighth;
614             final int p2 = p3 - eighth;
615             final int p1 = p2 - eighth;
616             final int p5 = p4 + eighth;
617             final int p6 = p5 + eighth;
618             final int p7 = p6 + eighth;
619             Sorting.sort7(data, p1, p2, p3, p4, p5, p6, p7);
620             pivot2[0] = p5;
621             return p3;
622         }
623 
624         @Override
625         int[] getSampledIndices(int left, int right) {
626             final int len = right - left;
627             final int eighth = Math.max(1, len >>> 3);
628             final int p4 = left + (len >>> 1);
629             final int p3 = p4 - eighth;
630             final int p2 = p3 - eighth;
631             final int p1 = p2 - eighth;
632             final int p5 = p4 + eighth;
633             final int p6 = p5 + eighth;
634             final int p7 = p6 + eighth;
635             return new int[] {p1, p2, p3, p4, p5, p6, p7};
636         }
637 
638         @Override
639         int samplingEffect() {
640             return SORT;
641         }
642     },
643     /**
644      * Pivot around the 3rd and 6th values from 8 approximately uniformly spaced within the range.
645      * Uses points +/- ninths from the median: m - 4/9, m - 3/9, m - 2/9, m - 1/9; m + 1 + 1/9,
646      * m + 1 + 2/9, m + 1 + 3/9, m + 1 + 4/9.
647      *
648      * <p>Requires {@code right - left >= 7}.
649      *
650      * <p>Warning: This has the side effect that the 8 values are also sorted.
651      *
652      * <p>On sorted data the tertiles are: 0.3380 0.6630
653      * <p>On random data the tertiles are:
654      * <pre>
655      *         min      max     mean       sd   median     skew
656      * [1]  0.0030   0.9480   0.3327   0.1485   0.3200   0.4044
657      * [2]  0.0050   0.9350   0.3345   0.1485   0.3220   0.4056
658      * [3]  0.0020   0.9320   0.3328   0.1485   0.3200   0.4063
659      * </pre>
660      */
661     SORT_8 {
662         @Override
663         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
664             // 1/9 = 4/36 = 8/72 ~ 7/64 ~ 1/16 + 1/32 + 1/64 : 0.11111 ~ 0.1094
665             // Ensure the value is above zero to choose different points!
666             // This is safe if len >= 7.
667             final int len = right - left;
668             final int ninth = Math.max(1, (len >>> 4) + (len >>> 5) + (len >>> 6));
669             // Work from middle outward. This is deliberate to ensure data.length==7
670             // throws an index out-of-bound exception.
671             final int m = left + (len >>> 1);
672             final int p4 = m - (ninth >> 1);
673             final int p3 = p4 - ninth;
674             final int p2 = p3 - ninth;
675             final int p1 = p2 - ninth;
676             final int p5 = m + (ninth >> 1) + 1;
677             final int p6 = p5 + ninth;
678             final int p7 = p6 + ninth;
679             final int p8 = p7 + ninth;
680             Sorting.sort8(data, p1, p2, p3, p4, p5, p6, p7, p8);
681             pivot2[0] = p6;
682             return p3;
683         }
684 
685         @Override
686         int[] getSampledIndices(int left, int right) {
687             final int len = right - left;
688             final int ninth = Math.max(1, (len >>> 4) + (len >>> 5) + (len >>> 6));
689             final int m = left + (len >>> 1);
690             final int p4 = m - (ninth >> 1);
691             final int p3 = p4 - ninth;
692             final int p2 = p3 - ninth;
693             final int p1 = p2 - ninth;
694             final int p5 = m + (ninth >> 1) + 1;
695             final int p6 = p5 + ninth;
696             final int p7 = p6 + ninth;
697             final int p8 = p7 + ninth;
698             return new int[] {p1, p2, p3, p4, p5, p6, p7, p8};
699         }
700 
701         @Override
702         int samplingEffect() {
703             return SORT;
704         }
705     },
706     /**
707      * Pivot around the 4th and 8th values from 11 approximately uniformly spaced within the range.
708      * Uses points +/- twelfths from the median: ..., m - 1/12, m, m + 1/12, ... .
709      *
710      * <p>Requires {@code right - left >= 10}.
711      *
712      * <p>Warning: This has the side effect that the 11 values are also sorted.
713      *
714      * <p>On sorted data the tertiles are: 0.3460 0.6540
715      * <p>On random data the tertiles are:
716      * <pre>
717      *         min      max     mean       sd   median     skew
718      * [1]  0.0060   0.9000   0.3328   0.1301   0.3230   0.3624
719      * [2]  0.0100   0.9190   0.3345   0.1299   0.3250   0.3643
720      * [3]  0.0060   0.8970   0.3327   0.1302   0.3230   0.3653
721      * </pre>
722      */
723     SORT_11 {
724         @Override
725         int pivotIndex(double[] data, int left, int right, int[] pivot2) {
726             // 1/12 = 8/96 ~ 1/16 + 1/32 ~ 9/96 : 0.8333 ~ 0.09375
727             // Ensure the value is above zero to choose different points!
728             // This is safe if len >= 10.
729             final int len = right - left;
730             final int twelfth = Math.max(1, (len >>> 4) + (len >>> 6));
731             final int p6 = left + (len >>> 1);
732             final int p5 = p6 - twelfth;
733             final int p4 = p5 - twelfth;
734             final int p3 = p4 - twelfth;
735             final int p2 = p3 - twelfth;
736             final int p1 = p2 - twelfth;
737             final int p7 = p6 + twelfth;
738             final int p8 = p7 + twelfth;
739             final int p9 = p8 + twelfth;
740             final int p10 = p9 + twelfth;
741             final int p11 = p10 + twelfth;
742             Sorting.sort11(data, p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11);
743             pivot2[0] = p8;
744             return p4;
745         }
746 
747         @Override
748         int[] getSampledIndices(int left, int right) {
749             final int len = right - left;
750             final int twelfth = Math.max(1, (len >>> 4) + (len >>> 6));
751             final int p6 = left + (len >>> 1);
752             final int p5 = p6 - twelfth;
753             final int p4 = p5 - twelfth;
754             final int p3 = p4 - twelfth;
755             final int p2 = p3 - twelfth;
756             final int p1 = p2 - twelfth;
757             final int p7 = p6 + twelfth;
758             final int p8 = p7 + twelfth;
759             final int p9 = p8 + twelfth;
760             final int p10 = p9 + twelfth;
761             final int p11 = p10 + twelfth;
762             return new int[] {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11};
763         }
764 
765         @Override
766         int samplingEffect() {
767             return SORT;
768         }
769     };
770 
771     /** Sampled points are unchanged. */
772     static final int UNCHANGED = 0;
773     /** Sampled points are partially sorted. */
774     static final int PARTIAL_SORT = 0x1;
775     /** Sampled points are sorted. */
776     static final int SORT = 0x2;
777 
778     /**
779      * Find two pivot indices of the array so that partitioning into 3-regions can be made.
780      *
781      * <pre>{@code
782      * left <= p1 <= p2 <= right
783      * }</pre>
784      *
785      * <p>Returns two pivots so that {@code data[p1] <= data[p2]}.
786      *
787      * @param data Array.
788      * @param left Lower bound (inclusive).
789      * @param right Upper bound (inclusive).
790      * @param pivot2 Second pivot.
791      * @return first pivot
792      */
793     abstract int pivotIndex(double[] data, int left, int right, int[] pivot2);
794 
795     // The following methods allow the strategy and side effects to be tested
796 
797     /**
798      * Get the indices of points that will be sampled.
799      *
800      * @param left Lower bound (inclusive).
801      * @param right Upper bound (inclusive).
802      * @return the indices
803      */
804     abstract int[] getSampledIndices(int left, int right);
805 
806     /**
807      * Get the effect on the sampled points.
808      * <ul>
809      * <li>0 - Unchanged
810      * <li>1 - Partially sorted
811      * <li>2 - Sorted
812      * </ul>
813      *
814      * @return the effect
815      */
816     abstract int samplingEffect();
817 }