DualPivotQuicksort源码

转x33g5p2x  于2021-12-30 转载在 其他  
字(60.4k)|赞(0)|评价(0)|浏览(419)
  1. package java.util;
  3. /** * This class implements the Dual-Pivot Quicksort algorithm by * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm * offers O(n log(n)) performance on many data sets that cause other * quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations. * * All exposed methods are package-private, designed to be invoked * from public methods (in class Arrays) after performing any * necessary array bounds checks and expanding parameters into the * required forms. * * @author Vladimir Yaroslavskiy * @author Jon Bentley * @author Josh Bloch * * @version 2011.02.11 m765.827.12i:5\7pm * @since 1.7 */
  4. final class DualPivotQuicksort {
  6.     /** * Prevents instantiation. */
  7.     private DualPivotQuicksort() {}
  9.     /* * Tuning parameters. */
  11.     /** * The maximum number of runs in merge sort. */
  12.     private static final int MAX_RUN_COUNT = 67;
  14.     /** * The maximum length of run in merge sort. */
  15.     private static final int MAX_RUN_LENGTH = 33;
  17.     /** * If the length of an array to be sorted is less than this * constant, Quicksort is used in preference to merge sort. */
  18.     private static final int QUICKSORT_THRESHOLD = 286;
  20.     /** * If the length of an array to be sorted is less than this * constant, insertion sort is used in preference to Quicksort. */
  21.     private static final int INSERTION_SORT_THRESHOLD = 47;
  23.     /** * If the length of a byte array to be sorted is greater than this * constant, counting sort is used in preference to insertion sort. */
  24.     private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
  26.     /** * If the length of a short or char array to be sorted is greater * than this constant, counting sort is used in preference to Quicksort. */
  27.     private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
  29.     /* * Sorting methods for seven primitive types. */
  31.     /** * Sorts the specified range of the array using the given * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  32.     static void sort(int[] a, int left, int right,
  33.                      int[] work, int workBase, int workLen) {
  34.         // Use Quicksort on small arrays
  35.         if (right - left < QUICKSORT_THRESHOLD) {
  36.             sort(a, left, right, true);
  37.             return;
  38.         }
  40.         /* * Index run[i] is the start of i-th run * (ascending or descending sequence). */
  41.         int[] run = new int[MAX_RUN_COUNT + 1];
  42.         int count = 0; run[0] = left;
  44.         // Check if the array is nearly sorted
  45.         for (int k = left; k < right; run[count] = k) {
  46.             if (a[k] < a[k + 1]) { // ascending
  47.                 while (++k <= right && a[k - 1] <= a[k]);
  48.             } else if (a[k] > a[k + 1]) { // descending
  49.                 while (++k <= right && a[k - 1] >= a[k]);
  50.                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  51.                     int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  52.                 }
  53.             } else { // equal
  54.                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  55.                     if (--m == 0) {
  56.                         sort(a, left, right, true);
  57.                         return;
  58.                     }
  59.                 }
  60.             }
  62.             /* * The array is not highly structured, * use Quicksort instead of merge sort. */
  63.             if (++count == MAX_RUN_COUNT) {
  64.                 sort(a, left, right, true);
  65.                 return;
  66.             }
  67.         }
  69.         // Check special cases
  70.         // Implementation note: variable "right" is increased by 1.
  71.         if (run[count] == right++) { // The last run contains one element
  72.             run[++count] = right;
  73.         } else if (count == 1) { // The array is already sorted
  74.             return;
  75.         }
  77.         // Determine alternation base for merge
  78.         byte odd = 0;
  79.         for (int n = 1; (n <<= 1) < count; odd ^= 1);
  81.         // Use or create temporary array b for merging
  82.         int[] b;                 // temp array; alternates with a
  83.         int ao, bo;              // array offsets from 'left'
  84.         int blen = right - left; // space needed for b
  85.         if (work == null || workLen < blen || workBase + blen > work.length) {
  86.             work = new int[blen];
  87.             workBase = 0;
  88.         }
  89.         if (odd == 0) {
  90.             System.arraycopy(a, left, work, workBase, blen);
  91.             b = a;
  92.             bo = 0;
  93.             a = work;
  94.             ao = workBase - left;
  95.         } else {
  96.             b = work;
  97.             ao = 0;
  98.             bo = workBase - left;
  99.         }
  101.         // Merging
  102.         for (int last; count > 1; count = last) {
  103.             for (int k = (last = 0) + 2; k <= count; k += 2) {
  104.                 int hi = run[k], mi = run[k - 1];
  105.                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
  106.                     if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
  107.                         b[i + bo] = a[p++ + ao];
  108.                     } else {
  109.                         b[i + bo] = a[q++ + ao];
  110.                     }
  111.                 }
  112.                 run[++last] = hi;
  113.             }
  114.             if ((count & 1) != 0) {
  115.                 for (int i = right, lo = run[count - 1]; --i >= lo;
  116.                     b[i + bo] = a[i + ao]
  117.                 );
  118.                 run[++last] = right;
  119.             }
  120.             int[] t = a; a = b; b = t;
  121.             int o = ao; ao = bo; bo = o;
  122.         }
  123.     }
  125.     /** * Sorts the specified range of the array by Dual-Pivot Quicksort. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param leftmost indicates if this part is the leftmost in the range */
  126.     private static void sort(int[] a, int left, int right, boolean leftmost) {
  127.         int length = right - left + 1;
  129.         // Use insertion sort on tiny arrays
  130.         if (length < INSERTION_SORT_THRESHOLD) {
  131.             if (leftmost) {
  132.                 /* * Traditional (without sentinel) insertion sort, * optimized for server VM, is used in case of * the leftmost part. */
  133.                 for (int i = left, j = i; i < right; j = ++i) {
  134.                     int ai = a[i + 1];
  135.                     while (ai < a[j]) {
  136.                         a[j + 1] = a[j];
  137.                         if (j-- == left) {
  138.                             break;
  139.                         }
  140.                     }
  141.                     a[j + 1] = ai;
  142.                 }
  143.             } else {
  144.                 /* * Skip the longest ascending sequence. */
  145.                 do {
  146.                     if (left >= right) {
  147.                         return;
  148.                     }
  149.                 } while (a[++left] >= a[left - 1]);
  151.                 /* * Every element from adjoining part plays the role * of sentinel, therefore this allows us to avoid the * left range check on each iteration. Moreover, we use * the more optimized algorithm, so called pair insertion * sort, which is faster (in the context of Quicksort) * than traditional implementation of insertion sort. */
  152.                 for (int k = left; ++left <= right; k = ++left) {
  153.                     int a1 = a[k], a2 = a[left];
  155.                     if (a1 < a2) {
  156.                         a2 = a1; a1 = a[left];
  157.                     }
  158.                     while (a1 < a[--k]) {
  159.                         a[k + 2] = a[k];
  160.                     }
  161.                     a[++k + 1] = a1;
  163.                     while (a2 < a[--k]) {
  164.                         a[k + 1] = a[k];
  165.                     }
  166.                     a[k + 1] = a2;
  167.                 }
  168.                 int last = a[right];
  170.                 while (last < a[--right]) {
  171.                     a[right + 1] = a[right];
  172.                 }
  173.                 a[right + 1] = last;
  174.             }
  175.             return;
  176.         }
  178.         // Inexpensive approximation of length / 7
  179.         int seventh = (length >> 3) + (length >> 6) + 1;
  181.         /* * Sort five evenly spaced elements around (and including) the * center element in the range. These elements will be used for * pivot selection as described below. The choice for spacing * these elements was empirically determined to work well on * a wide variety of inputs. */
  182.         int e3 = (left + right) >>> 1; // The midpoint
  183.         int e2 = e3 - seventh;
  184.         int e1 = e2 - seventh;
  185.         int e4 = e3 + seventh;
  186.         int e5 = e4 + seventh;
  188.         // Sort these elements using insertion sort
  189.         if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  191.         if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  192.             if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  193.         }
  194.         if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  195.             if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  196.                 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  197.             }
  198.         }
  199.         if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  200.             if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  201.                 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  202.                     if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  203.                 }
  204.             }
  205.         }
  207.         // Pointers
  208.         int less  = left;  // The index of the first element of center part
  209.         int great = right; // The index before the first element of right part
  211.         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  212.             /* * Use the second and fourth of the five sorted elements as pivots. * These values are inexpensive approximations of the first and * second terciles of the array. Note that pivot1 <= pivot2. */
  213.             int pivot1 = a[e2];
  214.             int pivot2 = a[e4];
  216.             /* * The first and the last elements to be sorted are moved to the * locations formerly occupied by the pivots. When partitioning * is complete, the pivots are swapped back into their final * positions, and excluded from subsequent sorting. */
  217.             a[e2] = a[left];
  218.             a[e4] = a[right];
  220.             /* * Skip elements, which are less or greater than pivot values. */
  221.             while (a[++less] < pivot1);
  222.             while (a[--great] > pivot2);
  224.             /* * Partitioning: * * left part center part right part * +--------------------------------------------------------------+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | * +--------------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot1 * pivot1 <= all in [less, k) <= pivot2 * all in (great, right) > pivot2 * * Pointer k is the first index of ?-part. */
  225.             outer:
  226.             for (int k = less - 1; ++k <= great; ) {
  227.                 int ak = a[k];
  228.                 if (ak < pivot1) { // Move a[k] to left part
  229.                     a[k] = a[less];
  230.                     /* * Here and below we use "a[i] = b; i++;" instead * of "a[i++] = b;" due to performance issue. */
  231.                     a[less] = ak;
  232.                     ++less;
  233.                 } else if (ak > pivot2) { // Move a[k] to right part
  234.                     while (a[great] > pivot2) {
  235.                         if (great-- == k) {
  236.                             break outer;
  237.                         }
  238.                     }
  239.                     if (a[great] < pivot1) { // a[great] <= pivot2
  240.                         a[k] = a[less];
  241.                         a[less] = a[great];
  242.                         ++less;
  243.                     } else { // pivot1 <= a[great] <= pivot2
  244.                         a[k] = a[great];
  245.                     }
  246.                     /* * Here and below we use "a[i] = b; i--;" instead * of "a[i--] = b;" due to performance issue. */
  247.                     a[great] = ak;
  248.                     --great;
  249.                 }
  250.             }
  252.             // Swap pivots into their final positions
  253.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  254.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  256.             // Sort left and right parts recursively, excluding known pivots
  257.             sort(a, left, less - 2, leftmost);
  258.             sort(a, great + 2, right, false);
  260.             /* * If center part is too large (comprises > 4/7 of the array), * swap internal pivot values to ends. */
  261.             if (less < e1 && e5 < great) {
  262.                 /* * Skip elements, which are equal to pivot values. */
  263.                 while (a[less] == pivot1) {
  264.                     ++less;
  265.                 }
  267.                 while (a[great] == pivot2) {
  268.                     --great;
  269.                 }
  271.                 /* * Partitioning: * * left part center part right part * +----------------------------------------------------------+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | * +----------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (*, less) == pivot1 * pivot1 < all in [less, k) < pivot2 * all in (great, *) == pivot2 * * Pointer k is the first index of ?-part. */
  272.                 outer:
  273.                 for (int k = less - 1; ++k <= great; ) {
  274.                     int ak = a[k];
  275.                     if (ak == pivot1) { // Move a[k] to left part
  276.                         a[k] = a[less];
  277.                         a[less] = ak;
  278.                         ++less;
  279.                     } else if (ak == pivot2) { // Move a[k] to right part
  280.                         while (a[great] == pivot2) {
  281.                             if (great-- == k) {
  282.                                 break outer;
  283.                             }
  284.                         }
  285.                         if (a[great] == pivot1) { // a[great] < pivot2
  286.                             a[k] = a[less];
  287.                             /* * Even though a[great] equals to pivot1, the * assignment a[less] = pivot1 may be incorrect, * if a[great] and pivot1 are floating-point zeros * of different signs. Therefore in float and * double sorting methods we have to use more * accurate assignment a[less] = a[great]. */
  288.                             a[less] = pivot1;
  289.                             ++less;
  290.                         } else { // pivot1 < a[great] < pivot2
  291.                             a[k] = a[great];
  292.                         }
  293.                         a[great] = ak;
  294.                         --great;
  295.                     }
  296.                 }
  297.             }
  299.             // Sort center part recursively
  300.             sort(a, less, great, false);
  302.         } else { // Partitioning with one pivot
  303.             /* * Use the third of the five sorted elements as pivot. * This value is inexpensive approximation of the median. */
  304.             int pivot = a[e3];
  306.             /* * Partitioning degenerates to the traditional 3-way * (or "Dutch National Flag") schema: * * left part center part right part * +-------------------------------------------------+ * | < pivot | == pivot | ? | > pivot | * +-------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot * all in [less, k) == pivot * all in (great, right) > pivot * * Pointer k is the first index of ?-part. */
  307.             for (int k = less; k <= great; ++k) {
  308.                 if (a[k] == pivot) {
  309.                     continue;
  310.                 }
  311.                 int ak = a[k];
  312.                 if (ak < pivot) { // Move a[k] to left part
  313.                     a[k] = a[less];
  314.                     a[less] = ak;
  315.                     ++less;
  316.                 } else { // a[k] > pivot - Move a[k] to right part
  317.                     while (a[great] > pivot) {
  318.                         --great;
  319.                     }
  320.                     if (a[great] < pivot) { // a[great] <= pivot
  321.                         a[k] = a[less];
  322.                         a[less] = a[great];
  323.                         ++less;
  324.                     } else { // a[great] == pivot
  325.                         /* * Even though a[great] equals to pivot, the * assignment a[k] = pivot may be incorrect, * if a[great] and pivot are floating-point * zeros of different signs. Therefore in float * and double sorting methods we have to use * more accurate assignment a[k] = a[great]. */
  326.                         a[k] = pivot;
  327.                     }
  328.                     a[great] = ak;
  329.                     --great;
  330.                 }
  331.             }
  333.             /* * Sort left and right parts recursively. * All elements from center part are equal * and, therefore, already sorted. */
  334.             sort(a, left, less - 1, leftmost);
  335.             sort(a, great + 1, right, false);
  336.         }
  337.     }
  339.     /** * Sorts the specified range of the array using the given * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  340.     static void sort(long[] a, int left, int right,
  341.                      long[] work, int workBase, int workLen) {
  342.         // Use Quicksort on small arrays
  343.         if (right - left < QUICKSORT_THRESHOLD) {
  344.             sort(a, left, right, true);
  345.             return;
  346.         }
  348.         /* * Index run[i] is the start of i-th run * (ascending or descending sequence). */
  349.         int[] run = new int[MAX_RUN_COUNT + 1];
  350.         int count = 0; run[0] = left;
  352.         // Check if the array is nearly sorted
  353.         for (int k = left; k < right; run[count] = k) {
  354.             if (a[k] < a[k + 1]) { // ascending
  355.                 while (++k <= right && a[k - 1] <= a[k]);
  356.             } else if (a[k] > a[k + 1]) { // descending
  357.                 while (++k <= right && a[k - 1] >= a[k]);
  358.                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  359.                     long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  360.                 }
  361.             } else { // equal
  362.                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  363.                     if (--m == 0) {
  364.                         sort(a, left, right, true);
  365.                         return;
  366.                     }
  367.                 }
  368.             }
  370.             /* * The array is not highly structured, * use Quicksort instead of merge sort. */
  371.             if (++count == MAX_RUN_COUNT) {
  372.                 sort(a, left, right, true);
  373.                 return;
  374.             }
  375.         }
  377.         // Check special cases
  378.         // Implementation note: variable "right" is increased by 1.
  379.         if (run[count] == right++) { // The last run contains one element
  380.             run[++count] = right;
  381.         } else if (count == 1) { // The array is already sorted
  382.             return;
  383.         }
  385.         // Determine alternation base for merge
  386.         byte odd = 0;
  387.         for (int n = 1; (n <<= 1) < count; odd ^= 1);
  389.         // Use or create temporary array b for merging
  390.         long[] b;                 // temp array; alternates with a
  391.         int ao, bo;              // array offsets from 'left'
  392.         int blen = right - left; // space needed for b
  393.         if (work == null || workLen < blen || workBase + blen > work.length) {
  394.             work = new long[blen];
  395.             workBase = 0;
  396.         }
  397.         if (odd == 0) {
  398.             System.arraycopy(a, left, work, workBase, blen);
  399.             b = a;
  400.             bo = 0;
  401.             a = work;
  402.             ao = workBase - left;
  403.         } else {
  404.             b = work;
  405.             ao = 0;
  406.             bo = workBase - left;
  407.         }
  409.         // Merging
  410.         for (int last; count > 1; count = last) {
  411.             for (int k = (last = 0) + 2; k <= count; k += 2) {
  412.                 int hi = run[k], mi = run[k - 1];
  413.                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
  414.                     if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
  415.                         b[i + bo] = a[p++ + ao];
  416.                     } else {
  417.                         b[i + bo] = a[q++ + ao];
  418.                     }
  419.                 }
  420.                 run[++last] = hi;
  421.             }
  422.             if ((count & 1) != 0) {
  423.                 for (int i = right, lo = run[count - 1]; --i >= lo;
  424.                     b[i + bo] = a[i + ao]
  425.                 );
  426.                 run[++last] = right;
  427.             }
  428.             long[] t = a; a = b; b = t;
  429.             int o = ao; ao = bo; bo = o;
  430.         }
  431.     }
  433.     /** * Sorts the specified range of the array by Dual-Pivot Quicksort. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param leftmost indicates if this part is the leftmost in the range */
  434.     private static void sort(long[] a, int left, int right, boolean leftmost) {
  435.         int length = right - left + 1;
  437.         // Use insertion sort on tiny arrays
  438.         if (length < INSERTION_SORT_THRESHOLD) {
  439.             if (leftmost) {
  440.                 /* * Traditional (without sentinel) insertion sort, * optimized for server VM, is used in case of * the leftmost part. */
  441.                 for (int i = left, j = i; i < right; j = ++i) {
  442.                     long ai = a[i + 1];
  443.                     while (ai < a[j]) {
  444.                         a[j + 1] = a[j];
  445.                         if (j-- == left) {
  446.                             break;
  447.                         }
  448.                     }
  449.                     a[j + 1] = ai;
  450.                 }
  451.             } else {
  452.                 /* * Skip the longest ascending sequence. */
  453.                 do {
  454.                     if (left >= right) {
  455.                         return;
  456.                     }
  457.                 } while (a[++left] >= a[left - 1]);
  459.                 /* * Every element from adjoining part plays the role * of sentinel, therefore this allows us to avoid the * left range check on each iteration. Moreover, we use * the more optimized algorithm, so called pair insertion * sort, which is faster (in the context of Quicksort) * than traditional implementation of insertion sort. */
  460.                 for (int k = left; ++left <= right; k = ++left) {
  461.                     long a1 = a[k], a2 = a[left];
  463.                     if (a1 < a2) {
  464.                         a2 = a1; a1 = a[left];
  465.                     }
  466.                     while (a1 < a[--k]) {
  467.                         a[k + 2] = a[k];
  468.                     }
  469.                     a[++k + 1] = a1;
  471.                     while (a2 < a[--k]) {
  472.                         a[k + 1] = a[k];
  473.                     }
  474.                     a[k + 1] = a2;
  475.                 }
  476.                 long last = a[right];
  478.                 while (last < a[--right]) {
  479.                     a[right + 1] = a[right];
  480.                 }
  481.                 a[right + 1] = last;
  482.             }
  483.             return;
  484.         }
  486.         // Inexpensive approximation of length / 7
  487.         int seventh = (length >> 3) + (length >> 6) + 1;
  489.         /* * Sort five evenly spaced elements around (and including) the * center element in the range. These elements will be used for * pivot selection as described below. The choice for spacing * these elements was empirically determined to work well on * a wide variety of inputs. */
  490.         int e3 = (left + right) >>> 1; // The midpoint
  491.         int e2 = e3 - seventh;
  492.         int e1 = e2 - seventh;
  493.         int e4 = e3 + seventh;
  494.         int e5 = e4 + seventh;
  496.         // Sort these elements using insertion sort
  497.         if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  499.         if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  500.             if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  501.         }
  502.         if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  503.             if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  504.                 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  505.             }
  506.         }
  507.         if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  508.             if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  509.                 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  510.                     if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  511.                 }
  512.             }
  513.         }
  515.         // Pointers
  516.         int less  = left;  // The index of the first element of center part
  517.         int great = right; // The index before the first element of right part
  519.         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  520.             /* * Use the second and fourth of the five sorted elements as pivots. * These values are inexpensive approximations of the first and * second terciles of the array. Note that pivot1 <= pivot2. */
  521.             long pivot1 = a[e2];
  522.             long pivot2 = a[e4];
  524.             /* * The first and the last elements to be sorted are moved to the * locations formerly occupied by the pivots. When partitioning * is complete, the pivots are swapped back into their final * positions, and excluded from subsequent sorting. */
  525.             a[e2] = a[left];
  526.             a[e4] = a[right];
  528.             /* * Skip elements, which are less or greater than pivot values. */
  529.             while (a[++less] < pivot1);
  530.             while (a[--great] > pivot2);
  532.             /* * Partitioning: * * left part center part right part * +--------------------------------------------------------------+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | * +--------------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot1 * pivot1 <= all in [less, k) <= pivot2 * all in (great, right) > pivot2 * * Pointer k is the first index of ?-part. */
  533.             outer:
  534.             for (int k = less - 1; ++k <= great; ) {
  535.                 long ak = a[k];
  536.                 if (ak < pivot1) { // Move a[k] to left part
  537.                     a[k] = a[less];
  538.                     /* * Here and below we use "a[i] = b; i++;" instead * of "a[i++] = b;" due to performance issue. */
  539.                     a[less] = ak;
  540.                     ++less;
  541.                 } else if (ak > pivot2) { // Move a[k] to right part
  542.                     while (a[great] > pivot2) {
  543.                         if (great-- == k) {
  544.                             break outer;
  545.                         }
  546.                     }
  547.                     if (a[great] < pivot1) { // a[great] <= pivot2
  548.                         a[k] = a[less];
  549.                         a[less] = a[great];
  550.                         ++less;
  551.                     } else { // pivot1 <= a[great] <= pivot2
  552.                         a[k] = a[great];
  553.                     }
  554.                     /* * Here and below we use "a[i] = b; i--;" instead * of "a[i--] = b;" due to performance issue. */
  555.                     a[great] = ak;
  556.                     --great;
  557.                 }
  558.             }
  560.             // Swap pivots into their final positions
  561.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  562.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  564.             // Sort left and right parts recursively, excluding known pivots
  565.             sort(a, left, less - 2, leftmost);
  566.             sort(a, great + 2, right, false);
  568.             /* * If center part is too large (comprises > 4/7 of the array), * swap internal pivot values to ends. */
  569.             if (less < e1 && e5 < great) {
  570.                 /* * Skip elements, which are equal to pivot values. */
  571.                 while (a[less] == pivot1) {
  572.                     ++less;
  573.                 }
  575.                 while (a[great] == pivot2) {
  576.                     --great;
  577.                 }
  579.                 /* * Partitioning: * * left part center part right part * +----------------------------------------------------------+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | * +----------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (*, less) == pivot1 * pivot1 < all in [less, k) < pivot2 * all in (great, *) == pivot2 * * Pointer k is the first index of ?-part. */
  580.                 outer:
  581.                 for (int k = less - 1; ++k <= great; ) {
  582.                     long ak = a[k];
  583.                     if (ak == pivot1) { // Move a[k] to left part
  584.                         a[k] = a[less];
  585.                         a[less] = ak;
  586.                         ++less;
  587.                     } else if (ak == pivot2) { // Move a[k] to right part
  588.                         while (a[great] == pivot2) {
  589.                             if (great-- == k) {
  590.                                 break outer;
  591.                             }
  592.                         }
  593.                         if (a[great] == pivot1) { // a[great] < pivot2
  594.                             a[k] = a[less];
  595.                             /* * Even though a[great] equals to pivot1, the * assignment a[less] = pivot1 may be incorrect, * if a[great] and pivot1 are floating-point zeros * of different signs. Therefore in float and * double sorting methods we have to use more * accurate assignment a[less] = a[great]. */
  596.                             a[less] = pivot1;
  597.                             ++less;
  598.                         } else { // pivot1 < a[great] < pivot2
  599.                             a[k] = a[great];
  600.                         }
  601.                         a[great] = ak;
  602.                         --great;
  603.                     }
  604.                 }
  605.             }
  607.             // Sort center part recursively
  608.             sort(a, less, great, false);
  610.         } else { // Partitioning with one pivot
  611.             /* * Use the third of the five sorted elements as pivot. * This value is inexpensive approximation of the median. */
  612.             long pivot = a[e3];
  614.             /* * Partitioning degenerates to the traditional 3-way * (or "Dutch National Flag") schema: * * left part center part right part * +-------------------------------------------------+ * | < pivot | == pivot | ? | > pivot | * +-------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot * all in [less, k) == pivot * all in (great, right) > pivot * * Pointer k is the first index of ?-part. */
  615.             for (int k = less; k <= great; ++k) {
  616.                 if (a[k] == pivot) {
  617.                     continue;
  618.                 }
  619.                 long ak = a[k];
  620.                 if (ak < pivot) { // Move a[k] to left part
  621.                     a[k] = a[less];
  622.                     a[less] = ak;
  623.                     ++less;
  624.                 } else { // a[k] > pivot - Move a[k] to right part
  625.                     while (a[great] > pivot) {
  626.                         --great;
  627.                     }
  628.                     if (a[great] < pivot) { // a[great] <= pivot
  629.                         a[k] = a[less];
  630.                         a[less] = a[great];
  631.                         ++less;
  632.                     } else { // a[great] == pivot
  633.                         /* * Even though a[great] equals to pivot, the * assignment a[k] = pivot may be incorrect, * if a[great] and pivot are floating-point * zeros of different signs. Therefore in float * and double sorting methods we have to use * more accurate assignment a[k] = a[great]. */
  634.                         a[k] = pivot;
  635.                     }
  636.                     a[great] = ak;
  637.                     --great;
  638.                 }
  639.             }
  641.             /* * Sort left and right parts recursively. * All elements from center part are equal * and, therefore, already sorted. */
  642.             sort(a, left, less - 1, leftmost);
  643.             sort(a, great + 1, right, false);
  644.         }
  645.     }
  647.     /** * Sorts the specified range of the array using the given * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  648.     static void sort(short[] a, int left, int right,
  649.                      short[] work, int workBase, int workLen) {
  650.         // Use counting sort on large arrays
  651.         if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
  652.             int[] count = new int[NUM_SHORT_VALUES];
  654.             for (int i = left - 1; ++i <= right;
  655.                 count[a[i] - Short.MIN_VALUE]++
  656.             );
  657.             for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {
  658.                 while (count[--i] == 0);
  659.                 short value = (short) (i + Short.MIN_VALUE);
  660.                 int s = count[i];
  662.                 do {
  663.                     a[--k] = value;
  664.                 } while (--s > 0);
  665.             }
  666.         } else { // Use Dual-Pivot Quicksort on small arrays
  667.             doSort(a, left, right, work, workBase, workLen);
  668.         }
  669.     }
  671.     /** The number of distinct short values. */
  672.     private static final int NUM_SHORT_VALUES = 1 << 16;
  674.     /** * Sorts the specified range of the array. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  675.     private static void doSort(short[] a, int left, int right,
  676.                                short[] work, int workBase, int workLen) {
  677.         // Use Quicksort on small arrays
  678.         if (right - left < QUICKSORT_THRESHOLD) {
  679.             sort(a, left, right, true);
  680.             return;
  681.         }
  683.         /* * Index run[i] is the start of i-th run * (ascending or descending sequence). */
  684.         int[] run = new int[MAX_RUN_COUNT + 1];
  685.         int count = 0; run[0] = left;
  687.         // Check if the array is nearly sorted
  688.         for (int k = left; k < right; run[count] = k) {
  689.             if (a[k] < a[k + 1]) { // ascending
  690.                 while (++k <= right && a[k - 1] <= a[k]);
  691.             } else if (a[k] > a[k + 1]) { // descending
  692.                 while (++k <= right && a[k - 1] >= a[k]);
  693.                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  694.                     short t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  695.                 }
  696.             } else { // equal
  697.                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  698.                     if (--m == 0) {
  699.                         sort(a, left, right, true);
  700.                         return;
  701.                     }
  702.                 }
  703.             }
  705.             /* * The array is not highly structured, * use Quicksort instead of merge sort. */
  706.             if (++count == MAX_RUN_COUNT) {
  707.                 sort(a, left, right, true);
  708.                 return;
  709.             }
  710.         }
  712.         // Check special cases
  713.         // Implementation note: variable "right" is increased by 1.
  714.         if (run[count] == right++) { // The last run contains one element
  715.             run[++count] = right;
  716.         } else if (count == 1) { // The array is already sorted
  717.             return;
  718.         }
  720.         // Determine alternation base for merge
  721.         byte odd = 0;
  722.         for (int n = 1; (n <<= 1) < count; odd ^= 1);
  724.         // Use or create temporary array b for merging
  725.         short[] b;                 // temp array; alternates with a
  726.         int ao, bo;              // array offsets from 'left'
  727.         int blen = right - left; // space needed for b
  728.         if (work == null || workLen < blen || workBase + blen > work.length) {
  729.             work = new short[blen];
  730.             workBase = 0;
  731.         }
  732.         if (odd == 0) {
  733.             System.arraycopy(a, left, work, workBase, blen);
  734.             b = a;
  735.             bo = 0;
  736.             a = work;
  737.             ao = workBase - left;
  738.         } else {
  739.             b = work;
  740.             ao = 0;
  741.             bo = workBase - left;
  742.         }
  744.         // Merging
  745.         for (int last; count > 1; count = last) {
  746.             for (int k = (last = 0) + 2; k <= count; k += 2) {
  747.                 int hi = run[k], mi = run[k - 1];
  748.                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
  749.                     if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
  750.                         b[i + bo] = a[p++ + ao];
  751.                     } else {
  752.                         b[i + bo] = a[q++ + ao];
  753.                     }
  754.                 }
  755.                 run[++last] = hi;
  756.             }
  757.             if ((count & 1) != 0) {
  758.                 for (int i = right, lo = run[count - 1]; --i >= lo;
  759.                     b[i + bo] = a[i + ao]
  760.                 );
  761.                 run[++last] = right;
  762.             }
  763.             short[] t = a; a = b; b = t;
  764.             int o = ao; ao = bo; bo = o;
  765.         }
  766.     }
  768.     /** * Sorts the specified range of the array by Dual-Pivot Quicksort. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param leftmost indicates if this part is the leftmost in the range */
  769.     private static void sort(short[] a, int left, int right, boolean leftmost) {
  770.         int length = right - left + 1;
  772.         // Use insertion sort on tiny arrays
  773.         if (length < INSERTION_SORT_THRESHOLD) {
  774.             if (leftmost) {
  775.                 /* * Traditional (without sentinel) insertion sort, * optimized for server VM, is used in case of * the leftmost part. */
  776.                 for (int i = left, j = i; i < right; j = ++i) {
  777.                     short ai = a[i + 1];
  778.                     while (ai < a[j]) {
  779.                         a[j + 1] = a[j];
  780.                         if (j-- == left) {
  781.                             break;
  782.                         }
  783.                     }
  784.                     a[j + 1] = ai;
  785.                 }
  786.             } else {
  787.                 /* * Skip the longest ascending sequence. */
  788.                 do {
  789.                     if (left >= right) {
  790.                         return;
  791.                     }
  792.                 } while (a[++left] >= a[left - 1]);
  794.                 /* * Every element from adjoining part plays the role * of sentinel, therefore this allows us to avoid the * left range check on each iteration. Moreover, we use * the more optimized algorithm, so called pair insertion * sort, which is faster (in the context of Quicksort) * than traditional implementation of insertion sort. */
  795.                 for (int k = left; ++left <= right; k = ++left) {
  796.                     short a1 = a[k], a2 = a[left];
  798.                     if (a1 < a2) {
  799.                         a2 = a1; a1 = a[left];
  800.                     }
  801.                     while (a1 < a[--k]) {
  802.                         a[k + 2] = a[k];
  803.                     }
  804.                     a[++k + 1] = a1;
  806.                     while (a2 < a[--k]) {
  807.                         a[k + 1] = a[k];
  808.                     }
  809.                     a[k + 1] = a2;
  810.                 }
  811.                 short last = a[right];
  813.                 while (last < a[--right]) {
  814.                     a[right + 1] = a[right];
  815.                 }
  816.                 a[right + 1] = last;
  817.             }
  818.             return;
  819.         }
  821.         // Inexpensive approximation of length / 7
  822.         int seventh = (length >> 3) + (length >> 6) + 1;
  824.         /* * Sort five evenly spaced elements around (and including) the * center element in the range. These elements will be used for * pivot selection as described below. The choice for spacing * these elements was empirically determined to work well on * a wide variety of inputs. */
  825.         int e3 = (left + right) >>> 1; // The midpoint
  826.         int e2 = e3 - seventh;
  827.         int e1 = e2 - seventh;
  828.         int e4 = e3 + seventh;
  829.         int e5 = e4 + seventh;
  831.         // Sort these elements using insertion sort
  832.         if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  834.         if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  835.             if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  836.         }
  837.         if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  838.             if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  839.                 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  840.             }
  841.         }
  842.         if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  843.             if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  844.                 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  845.                     if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  846.                 }
  847.             }
  848.         }
  850.         // Pointers
  851.         int less  = left;  // The index of the first element of center part
  852.         int great = right; // The index before the first element of right part
  854.         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  855.             /* * Use the second and fourth of the five sorted elements as pivots. * These values are inexpensive approximations of the first and * second terciles of the array. Note that pivot1 <= pivot2. */
  856.             short pivot1 = a[e2];
  857.             short pivot2 = a[e4];
  859.             /* * The first and the last elements to be sorted are moved to the * locations formerly occupied by the pivots. When partitioning * is complete, the pivots are swapped back into their final * positions, and excluded from subsequent sorting. */
  860.             a[e2] = a[left];
  861.             a[e4] = a[right];
  863.             /* * Skip elements, which are less or greater than pivot values. */
  864.             while (a[++less] < pivot1);
  865.             while (a[--great] > pivot2);
  867.             /* * Partitioning: * * left part center part right part * +--------------------------------------------------------------+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | * +--------------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot1 * pivot1 <= all in [less, k) <= pivot2 * all in (great, right) > pivot2 * * Pointer k is the first index of ?-part. */
  868.             outer:
  869.             for (int k = less - 1; ++k <= great; ) {
  870.                 short ak = a[k];
  871.                 if (ak < pivot1) { // Move a[k] to left part
  872.                     a[k] = a[less];
  873.                     /* * Here and below we use "a[i] = b; i++;" instead * of "a[i++] = b;" due to performance issue. */
  874.                     a[less] = ak;
  875.                     ++less;
  876.                 } else if (ak > pivot2) { // Move a[k] to right part
  877.                     while (a[great] > pivot2) {
  878.                         if (great-- == k) {
  879.                             break outer;
  880.                         }
  881.                     }
  882.                     if (a[great] < pivot1) { // a[great] <= pivot2
  883.                         a[k] = a[less];
  884.                         a[less] = a[great];
  885.                         ++less;
  886.                     } else { // pivot1 <= a[great] <= pivot2
  887.                         a[k] = a[great];
  888.                     }
  889.                     /* * Here and below we use "a[i] = b; i--;" instead * of "a[i--] = b;" due to performance issue. */
  890.                     a[great] = ak;
  891.                     --great;
  892.                 }
  893.             }
  895.             // Swap pivots into their final positions
  896.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  897.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  899.             // Sort left and right parts recursively, excluding known pivots
  900.             sort(a, left, less - 2, leftmost);
  901.             sort(a, great + 2, right, false);
  903.             /* * If center part is too large (comprises > 4/7 of the array), * swap internal pivot values to ends. */
  904.             if (less < e1 && e5 < great) {
  905.                 /* * Skip elements, which are equal to pivot values. */
  906.                 while (a[less] == pivot1) {
  907.                     ++less;
  908.                 }
  910.                 while (a[great] == pivot2) {
  911.                     --great;
  912.                 }
  914.                 /* * Partitioning: * * left part center part right part * +----------------------------------------------------------+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | * +----------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (*, less) == pivot1 * pivot1 < all in [less, k) < pivot2 * all in (great, *) == pivot2 * * Pointer k is the first index of ?-part. */
  915.                 outer:
  916.                 for (int k = less - 1; ++k <= great; ) {
  917.                     short ak = a[k];
  918.                     if (ak == pivot1) { // Move a[k] to left part
  919.                         a[k] = a[less];
  920.                         a[less] = ak;
  921.                         ++less;
  922.                     } else if (ak == pivot2) { // Move a[k] to right part
  923.                         while (a[great] == pivot2) {
  924.                             if (great-- == k) {
  925.                                 break outer;
  926.                             }
  927.                         }
  928.                         if (a[great] == pivot1) { // a[great] < pivot2
  929.                             a[k] = a[less];
  930.                             /* * Even though a[great] equals to pivot1, the * assignment a[less] = pivot1 may be incorrect, * if a[great] and pivot1 are floating-point zeros * of different signs. Therefore in float and * double sorting methods we have to use more * accurate assignment a[less] = a[great]. */
  931.                             a[less] = pivot1;
  932.                             ++less;
  933.                         } else { // pivot1 < a[great] < pivot2
  934.                             a[k] = a[great];
  935.                         }
  936.                         a[great] = ak;
  937.                         --great;
  938.                     }
  939.                 }
  940.             }
  942.             // Sort center part recursively
  943.             sort(a, less, great, false);
  945.         } else { // Partitioning with one pivot
  946.             /* * Use the third of the five sorted elements as pivot. * This value is inexpensive approximation of the median. */
  947.             short pivot = a[e3];
  949.             /* * Partitioning degenerates to the traditional 3-way * (or "Dutch National Flag") schema: * * left part center part right part * +-------------------------------------------------+ * | < pivot | == pivot | ? | > pivot | * +-------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot * all in [less, k) == pivot * all in (great, right) > pivot * * Pointer k is the first index of ?-part. */
  950.             for (int k = less; k <= great; ++k) {
  951.                 if (a[k] == pivot) {
  952.                     continue;
  953.                 }
  954.                 short ak = a[k];
  955.                 if (ak < pivot) { // Move a[k] to left part
  956.                     a[k] = a[less];
  957.                     a[less] = ak;
  958.                     ++less;
  959.                 } else { // a[k] > pivot - Move a[k] to right part
  960.                     while (a[great] > pivot) {
  961.                         --great;
  962.                     }
  963.                     if (a[great] < pivot) { // a[great] <= pivot
  964.                         a[k] = a[less];
  965.                         a[less] = a[great];
  966.                         ++less;
  967.                     } else { // a[great] == pivot
  968.                         /* * Even though a[great] equals to pivot, the * assignment a[k] = pivot may be incorrect, * if a[great] and pivot are floating-point * zeros of different signs. Therefore in float * and double sorting methods we have to use * more accurate assignment a[k] = a[great]. */
  969.                         a[k] = pivot;
  970.                     }
  971.                     a[great] = ak;
  972.                     --great;
  973.                 }
  974.             }
  976.             /* * Sort left and right parts recursively. * All elements from center part are equal * and, therefore, already sorted. */
  977.             sort(a, left, less - 1, leftmost);
  978.             sort(a, great + 1, right, false);
  979.         }
  980.     }
  982.     /** * Sorts the specified range of the array using the given * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  983.     static void sort(char[] a, int left, int right,
  984.                      char[] work, int workBase, int workLen) {
  985.         // Use counting sort on large arrays
  986.         if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
  987.             int[] count = new int[NUM_CHAR_VALUES];
  989.             for (int i = left - 1; ++i <= right;
  990.                 count[a[i]]++
  991.             );
  992.             for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
  993.                 while (count[--i] == 0);
  994.                 char value = (char) i;
  995.                 int s = count[i];
  997.                 do {
  998.                     a[--k] = value;
  999.                 } while (--s > 0);
  1000.             }
  1001.         } else { // Use Dual-Pivot Quicksort on small arrays
  1002.             doSort(a, left, right, work, workBase, workLen);
  1003.         }
  1004.     }
  1006.     /** The number of distinct char values. */
  1007.     private static final int NUM_CHAR_VALUES = 1 << 16;
  1009.     /** * Sorts the specified range of the array. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  1010.     private static void doSort(char[] a, int left, int right,
  1011.                                char[] work, int workBase, int workLen) {
  1012.         // Use Quicksort on small arrays
  1013.         if (right - left < QUICKSORT_THRESHOLD) {
  1014.             sort(a, left, right, true);
  1015.             return;
  1016.         }
  1018.         /* * Index run[i] is the start of i-th run * (ascending or descending sequence). */
  1019.         int[] run = new int[MAX_RUN_COUNT + 1];
  1020.         int count = 0; run[0] = left;
  1022.         // Check if the array is nearly sorted
  1023.         for (int k = left; k < right; run[count] = k) {
  1024.             if (a[k] < a[k + 1]) { // ascending
  1025.                 while (++k <= right && a[k - 1] <= a[k]);
  1026.             } else if (a[k] > a[k + 1]) { // descending
  1027.                 while (++k <= right && a[k - 1] >= a[k]);
  1028.                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  1029.                     char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  1030.                 }
  1031.             } else { // equal
  1032.                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  1033.                     if (--m == 0) {
  1034.                         sort(a, left, right, true);
  1035.                         return;
  1036.                     }
  1037.                 }
  1038.             }
  1040.             /* * The array is not highly structured, * use Quicksort instead of merge sort. */
  1041.             if (++count == MAX_RUN_COUNT) {
  1042.                 sort(a, left, right, true);
  1043.                 return;
  1044.             }
  1045.         }
  1047.         // Check special cases
  1048.         // Implementation note: variable "right" is increased by 1.
  1049.         if (run[count] == right++) { // The last run contains one element
  1050.             run[++count] = right;
  1051.         } else if (count == 1) { // The array is already sorted
  1052.             return;
  1053.         }
  1055.         // Determine alternation base for merge
  1056.         byte odd = 0;
  1057.         for (int n = 1; (n <<= 1) < count; odd ^= 1);
  1059.         // Use or create temporary array b for merging
  1060.         char[] b;                 // temp array; alternates with a
  1061.         int ao, bo;              // array offsets from 'left'
  1062.         int blen = right - left; // space needed for b
  1063.         if (work == null || workLen < blen || workBase + blen > work.length) {
  1064.             work = new char[blen];
  1065.             workBase = 0;
  1066.         }
  1067.         if (odd == 0) {
  1068.             System.arraycopy(a, left, work, workBase, blen);
  1069.             b = a;
  1070.             bo = 0;
  1071.             a = work;
  1072.             ao = workBase - left;
  1073.         } else {
  1074.             b = work;
  1075.             ao = 0;
  1076.             bo = workBase - left;
  1077.         }
  1079.         // Merging
  1080.         for (int last; count > 1; count = last) {
  1081.             for (int k = (last = 0) + 2; k <= count; k += 2) {
  1082.                 int hi = run[k], mi = run[k - 1];
  1083.                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
  1084.                     if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
  1085.                         b[i + bo] = a[p++ + ao];
  1086.                     } else {
  1087.                         b[i + bo] = a[q++ + ao];
  1088.                     }
  1089.                 }
  1090.                 run[++last] = hi;
  1091.             }
  1092.             if ((count & 1) != 0) {
  1093.                 for (int i = right, lo = run[count - 1]; --i >= lo;
  1094.                     b[i + bo] = a[i + ao]
  1095.                 );
  1096.                 run[++last] = right;
  1097.             }
  1098.             char[] t = a; a = b; b = t;
  1099.             int o = ao; ao = bo; bo = o;
  1100.         }
  1101.     }
  1103.     /** * Sorts the specified range of the array by Dual-Pivot Quicksort. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param leftmost indicates if this part is the leftmost in the range */
  1104.     private static void sort(char[] a, int left, int right, boolean leftmost) {
  1105.         int length = right - left + 1;
  1107.         // Use insertion sort on tiny arrays
  1108.         if (length < INSERTION_SORT_THRESHOLD) {
  1109.             if (leftmost) {
  1110.                 /* * Traditional (without sentinel) insertion sort, * optimized for server VM, is used in case of * the leftmost part. */
  1111.                 for (int i = left, j = i; i < right; j = ++i) {
  1112.                     char ai = a[i + 1];
  1113.                     while (ai < a[j]) {
  1114.                         a[j + 1] = a[j];
  1115.                         if (j-- == left) {
  1116.                             break;
  1117.                         }
  1118.                     }
  1119.                     a[j + 1] = ai;
  1120.                 }
  1121.             } else {
  1122.                 /* * Skip the longest ascending sequence. */
  1123.                 do {
  1124.                     if (left >= right) {
  1125.                         return;
  1126.                     }
  1127.                 } while (a[++left] >= a[left - 1]);
  1129.                 /* * Every element from adjoining part plays the role * of sentinel, therefore this allows us to avoid the * left range check on each iteration. Moreover, we use * the more optimized algorithm, so called pair insertion * sort, which is faster (in the context of Quicksort) * than traditional implementation of insertion sort. */
  1130.                 for (int k = left; ++left <= right; k = ++left) {
  1131.                     char a1 = a[k], a2 = a[left];
  1133.                     if (a1 < a2) {
  1134.                         a2 = a1; a1 = a[left];
  1135.                     }
  1136.                     while (a1 < a[--k]) {
  1137.                         a[k + 2] = a[k];
  1138.                     }
  1139.                     a[++k + 1] = a1;
  1141.                     while (a2 < a[--k]) {
  1142.                         a[k + 1] = a[k];
  1143.                     }
  1144.                     a[k + 1] = a2;
  1145.                 }
  1146.                 char last = a[right];
  1148.                 while (last < a[--right]) {
  1149.                     a[right + 1] = a[right];
  1150.                 }
  1151.                 a[right + 1] = last;
  1152.             }
  1153.             return;
  1154.         }
  1156.         // Inexpensive approximation of length / 7
  1157.         int seventh = (length >> 3) + (length >> 6) + 1;
  1159.         /* * Sort five evenly spaced elements around (and including) the * center element in the range. These elements will be used for * pivot selection as described below. The choice for spacing * these elements was empirically determined to work well on * a wide variety of inputs. */
  1160.         int e3 = (left + right) >>> 1; // The midpoint
  1161.         int e2 = e3 - seventh;
  1162.         int e1 = e2 - seventh;
  1163.         int e4 = e3 + seventh;
  1164.         int e5 = e4 + seventh;
  1166.         // Sort these elements using insertion sort
  1167.         if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  1169.         if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  1170.             if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  1171.         }
  1172.         if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  1173.             if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  1174.                 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  1175.             }
  1176.         }
  1177.         if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  1178.             if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  1179.                 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  1180.                     if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  1181.                 }
  1182.             }
  1183.         }
  1185.         // Pointers
  1186.         int less  = left;  // The index of the first element of center part
  1187.         int great = right; // The index before the first element of right part
  1189.         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  1190.             /* * Use the second and fourth of the five sorted elements as pivots. * These values are inexpensive approximations of the first and * second terciles of the array. Note that pivot1 <= pivot2. */
  1191.             char pivot1 = a[e2];
  1192.             char pivot2 = a[e4];
  1194.             /* * The first and the last elements to be sorted are moved to the * locations formerly occupied by the pivots. When partitioning * is complete, the pivots are swapped back into their final * positions, and excluded from subsequent sorting. */
  1195.             a[e2] = a[left];
  1196.             a[e4] = a[right];
  1198.             /* * Skip elements, which are less or greater than pivot values. */
  1199.             while (a[++less] < pivot1);
  1200.             while (a[--great] > pivot2);
  1202.             /* * Partitioning: * * left part center part right part * +--------------------------------------------------------------+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | * +--------------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot1 * pivot1 <= all in [less, k) <= pivot2 * all in (great, right) > pivot2 * * Pointer k is the first index of ?-part. */
  1203.             outer:
  1204.             for (int k = less - 1; ++k <= great; ) {
  1205.                 char ak = a[k];
  1206.                 if (ak < pivot1) { // Move a[k] to left part
  1207.                     a[k] = a[less];
  1208.                     /* * Here and below we use "a[i] = b; i++;" instead * of "a[i++] = b;" due to performance issue. */
  1209.                     a[less] = ak;
  1210.                     ++less;
  1211.                 } else if (ak > pivot2) { // Move a[k] to right part
  1212.                     while (a[great] > pivot2) {
  1213.                         if (great-- == k) {
  1214.                             break outer;
  1215.                         }
  1216.                     }
  1217.                     if (a[great] < pivot1) { // a[great] <= pivot2
  1218.                         a[k] = a[less];
  1219.                         a[less] = a[great];
  1220.                         ++less;
  1221.                     } else { // pivot1 <= a[great] <= pivot2
  1222.                         a[k] = a[great];
  1223.                     }
  1224.                     /* * Here and below we use "a[i] = b; i--;" instead * of "a[i--] = b;" due to performance issue. */
  1225.                     a[great] = ak;
  1226.                     --great;
  1227.                 }
  1228.             }
  1230.             // Swap pivots into their final positions
  1231.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  1232.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  1234.             // Sort left and right parts recursively, excluding known pivots
  1235.             sort(a, left, less - 2, leftmost);
  1236.             sort(a, great + 2, right, false);
  1238.             /* * If center part is too large (comprises > 4/7 of the array), * swap internal pivot values to ends. */
  1239.             if (less < e1 && e5 < great) {
  1240.                 /* * Skip elements, which are equal to pivot values. */
  1241.                 while (a[less] == pivot1) {
  1242.                     ++less;
  1243.                 }
  1245.                 while (a[great] == pivot2) {
  1246.                     --great;
  1247.                 }
  1249.                 /* * Partitioning: * * left part center part right part * +----------------------------------------------------------+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | * +----------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (*, less) == pivot1 * pivot1 < all in [less, k) < pivot2 * all in (great, *) == pivot2 * * Pointer k is the first index of ?-part. */
  1250.                 outer:
  1251.                 for (int k = less - 1; ++k <= great; ) {
  1252.                     char ak = a[k];
  1253.                     if (ak == pivot1) { // Move a[k] to left part
  1254.                         a[k] = a[less];
  1255.                         a[less] = ak;
  1256.                         ++less;
  1257.                     } else if (ak == pivot2) { // Move a[k] to right part
  1258.                         while (a[great] == pivot2) {
  1259.                             if (great-- == k) {
  1260.                                 break outer;
  1261.                             }
  1262.                         }
  1263.                         if (a[great] == pivot1) { // a[great] < pivot2
  1264.                             a[k] = a[less];
  1265.                             /* * Even though a[great] equals to pivot1, the * assignment a[less] = pivot1 may be incorrect, * if a[great] and pivot1 are floating-point zeros * of different signs. Therefore in float and * double sorting methods we have to use more * accurate assignment a[less] = a[great]. */
  1266.                             a[less] = pivot1;
  1267.                             ++less;
  1268.                         } else { // pivot1 < a[great] < pivot2
  1269.                             a[k] = a[great];
  1270.                         }
  1271.                         a[great] = ak;
  1272.                         --great;
  1273.                     }
  1274.                 }
  1275.             }
  1277.             // Sort center part recursively
  1278.             sort(a, less, great, false);
  1280.         } else { // Partitioning with one pivot
  1281.             /* * Use the third of the five sorted elements as pivot. * This value is inexpensive approximation of the median. */
  1282.             char pivot = a[e3];
  1284.             /* * Partitioning degenerates to the traditional 3-way * (or "Dutch National Flag") schema: * * left part center part right part * +-------------------------------------------------+ * | < pivot | == pivot | ? | > pivot | * +-------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot * all in [less, k) == pivot * all in (great, right) > pivot * * Pointer k is the first index of ?-part. */
  1285.             for (int k = less; k <= great; ++k) {
  1286.                 if (a[k] == pivot) {
  1287.                     continue;
  1288.                 }
  1289.                 char ak = a[k];
  1290.                 if (ak < pivot) { // Move a[k] to left part
  1291.                     a[k] = a[less];
  1292.                     a[less] = ak;
  1293.                     ++less;
  1294.                 } else { // a[k] > pivot - Move a[k] to right part
  1295.                     while (a[great] > pivot) {
  1296.                         --great;
  1297.                     }
  1298.                     if (a[great] < pivot) { // a[great] <= pivot
  1299.                         a[k] = a[less];
  1300.                         a[less] = a[great];
  1301.                         ++less;
  1302.                     } else { // a[great] == pivot
  1303.                         /* * Even though a[great] equals to pivot, the * assignment a[k] = pivot may be incorrect, * if a[great] and pivot are floating-point * zeros of different signs. Therefore in float * and double sorting methods we have to use * more accurate assignment a[k] = a[great]. */
  1304.                         a[k] = pivot;
  1305.                     }
  1306.                     a[great] = ak;
  1307.                     --great;
  1308.                 }
  1309.             }
  1311.             /* * Sort left and right parts recursively. * All elements from center part are equal * and, therefore, already sorted. */
  1312.             sort(a, left, less - 1, leftmost);
  1313.             sort(a, great + 1, right, false);
  1314.         }
  1315.     }
  1317.     /** The number of distinct byte values. */
  1318.     private static final int NUM_BYTE_VALUES = 1 << 8;
  1320.     /** * Sorts the specified range of the array. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted */
  1321.     static void sort(byte[] a, int left, int right) {
  1322.         // Use counting sort on large arrays
  1323.         if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
  1324.             int[] count = new int[NUM_BYTE_VALUES];
  1326.             for (int i = left - 1; ++i <= right;
  1327.                 count[a[i] - Byte.MIN_VALUE]++
  1328.             );
  1329.             for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
  1330.                 while (count[--i] == 0);
  1331.                 byte value = (byte) (i + Byte.MIN_VALUE);
  1332.                 int s = count[i];
  1334.                 do {
  1335.                     a[--k] = value;
  1336.                 } while (--s > 0);
  1337.             }
  1338.         } else { // Use insertion sort on small arrays
  1339.             for (int i = left, j = i; i < right; j = ++i) {
  1340.                 byte ai = a[i + 1];
  1341.                 while (ai < a[j]) {
  1342.                     a[j + 1] = a[j];
  1343.                     if (j-- == left) {
  1344.                         break;
  1345.                     }
  1346.                 }
  1347.                 a[j + 1] = ai;
  1348.             }
  1349.         }
  1350.     }
  1352.     /** * Sorts the specified range of the array using the given * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  1353.     static void sort(float[] a, int left, int right,
  1354.                      float[] work, int workBase, int workLen) {
  1355.         /* * Phase 1: Move NaNs to the end of the array. */
  1356.         while (left <= right && Float.isNaN(a[right])) {
  1357.             --right;
  1358.         }
  1359.         for (int k = right; --k >= left; ) {
  1360.             float ak = a[k];
  1361.             if (ak != ak) { // a[k] is NaN
  1362.                 a[k] = a[right];
  1363.                 a[right] = ak;
  1364.                 --right;
  1365.             }
  1366.         }
  1368.         /* * Phase 2: Sort everything except NaNs (which are already in place). */
  1369.         doSort(a, left, right, work, workBase, workLen);
  1371.         /* * Phase 3: Place negative zeros before positive zeros. */
  1372.         int hi = right;
  1374.         /* * Find the first zero, or first positive, or last negative element. */
  1375.         while (left < hi) {
  1376.             int middle = (left + hi) >>> 1;
  1377.             float middleValue = a[middle];
  1379.             if (middleValue < 0.0f) {
  1380.                 left = middle + 1;
  1381.             } else {
  1382.                 hi = middle;
  1383.             }
  1384.         }
  1386.         /* * Skip the last negative value (if any) or all leading negative zeros. */
  1387.         while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
  1388.             ++left;
  1389.         }
  1391.         /* * Move negative zeros to the beginning of the sub-range. * * Partitioning: * * +----------------------------------------------------+ * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) | * +----------------------------------------------------+ * ^ ^ ^ * | | | * left p k * * Invariants: * * all in (*, left) < 0.0 * all in [left, p) == -0.0 * all in [p, k) == 0.0 * all in [k, right] >= 0.0 * * Pointer k is the first index of ?-part. */
  1392.         for (int k = left, p = left - 1; ++k <= right; ) {
  1393.             float ak = a[k];
  1394.             if (ak != 0.0f) {
  1395.                 break;
  1396.             }
  1397.             if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
  1398.                 a[k] = 0.0f;
  1399.                 a[++p] = -0.0f;
  1400.             }
  1401.         }
  1402.     }
  1404.     /** * Sorts the specified range of the array. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  1405.     private static void doSort(float[] a, int left, int right,
  1406.                                float[] work, int workBase, int workLen) {
  1407.         // Use Quicksort on small arrays
  1408.         if (right - left < QUICKSORT_THRESHOLD) {
  1409.             sort(a, left, right, true);
  1410.             return;
  1411.         }
  1413.         /* * Index run[i] is the start of i-th run * (ascending or descending sequence). */
  1414.         int[] run = new int[MAX_RUN_COUNT + 1];
  1415.         int count = 0; run[0] = left;
  1417.         // Check if the array is nearly sorted
  1418.         for (int k = left; k < right; run[count] = k) {
  1419.             if (a[k] < a[k + 1]) { // ascending
  1420.                 while (++k <= right && a[k - 1] <= a[k]);
  1421.             } else if (a[k] > a[k + 1]) { // descending
  1422.                 while (++k <= right && a[k - 1] >= a[k]);
  1423.                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  1424.                     float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  1425.                 }
  1426.             } else { // equal
  1427.                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  1428.                     if (--m == 0) {
  1429.                         sort(a, left, right, true);
  1430.                         return;
  1431.                     }
  1432.                 }
  1433.             }
  1435.             /* * The array is not highly structured, * use Quicksort instead of merge sort. */
  1436.             if (++count == MAX_RUN_COUNT) {
  1437.                 sort(a, left, right, true);
  1438.                 return;
  1439.             }
  1440.         }
  1442.         // Check special cases
  1443.         // Implementation note: variable "right" is increased by 1.
  1444.         if (run[count] == right++) { // The last run contains one element
  1445.             run[++count] = right;
  1446.         } else if (count == 1) { // The array is already sorted
  1447.             return;
  1448.         }
  1450.         // Determine alternation base for merge
  1451.         byte odd = 0;
  1452.         for (int n = 1; (n <<= 1) < count; odd ^= 1);
  1454.         // Use or create temporary array b for merging
  1455.         float[] b;                 // temp array; alternates with a
  1456.         int ao, bo;              // array offsets from 'left'
  1457.         int blen = right - left; // space needed for b
  1458.         if (work == null || workLen < blen || workBase + blen > work.length) {
  1459.             work = new float[blen];
  1460.             workBase = 0;
  1461.         }
  1462.         if (odd == 0) {
  1463.             System.arraycopy(a, left, work, workBase, blen);
  1464.             b = a;
  1465.             bo = 0;
  1466.             a = work;
  1467.             ao = workBase - left;
  1468.         } else {
  1469.             b = work;
  1470.             ao = 0;
  1471.             bo = workBase - left;
  1472.         }
  1474.         // Merging
  1475.         for (int last; count > 1; count = last) {
  1476.             for (int k = (last = 0) + 2; k <= count; k += 2) {
  1477.                 int hi = run[k], mi = run[k - 1];
  1478.                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
  1479.                     if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
  1480.                         b[i + bo] = a[p++ + ao];
  1481.                     } else {
  1482.                         b[i + bo] = a[q++ + ao];
  1483.                     }
  1484.                 }
  1485.                 run[++last] = hi;
  1486.             }
  1487.             if ((count & 1) != 0) {
  1488.                 for (int i = right, lo = run[count - 1]; --i >= lo;
  1489.                     b[i + bo] = a[i + ao]
  1490.                 );
  1491.                 run[++last] = right;
  1492.             }
  1493.             float[] t = a; a = b; b = t;
  1494.             int o = ao; ao = bo; bo = o;
  1495.         }
  1496.     }
  1498.     /** * Sorts the specified range of the array by Dual-Pivot Quicksort. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param leftmost indicates if this part is the leftmost in the range */
  1499.     private static void sort(float[] a, int left, int right, boolean leftmost) {
  1500.         int length = right - left + 1;
  1502.         // Use insertion sort on tiny arrays
  1503.         if (length < INSERTION_SORT_THRESHOLD) {
  1504.             if (leftmost) {
  1505.                 /* * Traditional (without sentinel) insertion sort, * optimized for server VM, is used in case of * the leftmost part. */
  1506.                 for (int i = left, j = i; i < right; j = ++i) {
  1507.                     float ai = a[i + 1];
  1508.                     while (ai < a[j]) {
  1509.                         a[j + 1] = a[j];
  1510.                         if (j-- == left) {
  1511.                             break;
  1512.                         }
  1513.                     }
  1514.                     a[j + 1] = ai;
  1515.                 }
  1516.             } else {
  1517.                 /* * Skip the longest ascending sequence. */
  1518.                 do {
  1519.                     if (left >= right) {
  1520.                         return;
  1521.                     }
  1522.                 } while (a[++left] >= a[left - 1]);
  1524.                 /* * Every element from adjoining part plays the role * of sentinel, therefore this allows us to avoid the * left range check on each iteration. Moreover, we use * the more optimized algorithm, so called pair insertion * sort, which is faster (in the context of Quicksort) * than traditional implementation of insertion sort. */
  1525.                 for (int k = left; ++left <= right; k = ++left) {
  1526.                     float a1 = a[k], a2 = a[left];
  1528.                     if (a1 < a2) {
  1529.                         a2 = a1; a1 = a[left];
  1530.                     }
  1531.                     while (a1 < a[--k]) {
  1532.                         a[k + 2] = a[k];
  1533.                     }
  1534.                     a[++k + 1] = a1;
  1536.                     while (a2 < a[--k]) {
  1537.                         a[k + 1] = a[k];
  1538.                     }
  1539.                     a[k + 1] = a2;
  1540.                 }
  1541.                 float last = a[right];
  1543.                 while (last < a[--right]) {
  1544.                     a[right + 1] = a[right];
  1545.                 }
  1546.                 a[right + 1] = last;
  1547.             }
  1548.             return;
  1549.         }
  1551.         // Inexpensive approximation of length / 7
  1552.         int seventh = (length >> 3) + (length >> 6) + 1;
  1554.         /* * Sort five evenly spaced elements around (and including) the * center element in the range. These elements will be used for * pivot selection as described below. The choice for spacing * these elements was empirically determined to work well on * a wide variety of inputs. */
  1555.         int e3 = (left + right) >>> 1; // The midpoint
  1556.         int e2 = e3 - seventh;
  1557.         int e1 = e2 - seventh;
  1558.         int e4 = e3 + seventh;
  1559.         int e5 = e4 + seventh;
  1561.         // Sort these elements using insertion sort
  1562.         if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  1564.         if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  1565.             if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  1566.         }
  1567.         if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  1568.             if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  1569.                 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  1570.             }
  1571.         }
  1572.         if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  1573.             if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  1574.                 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  1575.                     if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  1576.                 }
  1577.             }
  1578.         }
  1580.         // Pointers
  1581.         int less  = left;  // The index of the first element of center part
  1582.         int great = right; // The index before the first element of right part
  1584.         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  1585.             /* * Use the second and fourth of the five sorted elements as pivots. * These values are inexpensive approximations of the first and * second terciles of the array. Note that pivot1 <= pivot2. */
  1586.             float pivot1 = a[e2];
  1587.             float pivot2 = a[e4];
  1589.             /* * The first and the last elements to be sorted are moved to the * locations formerly occupied by the pivots. When partitioning * is complete, the pivots are swapped back into their final * positions, and excluded from subsequent sorting. */
  1590.             a[e2] = a[left];
  1591.             a[e4] = a[right];
  1593.             /* * Skip elements, which are less or greater than pivot values. */
  1594.             while (a[++less] < pivot1);
  1595.             while (a[--great] > pivot2);
  1597.             /* * Partitioning: * * left part center part right part * +--------------------------------------------------------------+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | * +--------------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot1 * pivot1 <= all in [less, k) <= pivot2 * all in (great, right) > pivot2 * * Pointer k is the first index of ?-part. */
  1598.             outer:
  1599.             for (int k = less - 1; ++k <= great; ) {
  1600.                 float ak = a[k];
  1601.                 if (ak < pivot1) { // Move a[k] to left part
  1602.                     a[k] = a[less];
  1603.                     /* * Here and below we use "a[i] = b; i++;" instead * of "a[i++] = b;" due to performance issue. */
  1604.                     a[less] = ak;
  1605.                     ++less;
  1606.                 } else if (ak > pivot2) { // Move a[k] to right part
  1607.                     while (a[great] > pivot2) {
  1608.                         if (great-- == k) {
  1609.                             break outer;
  1610.                         }
  1611.                     }
  1612.                     if (a[great] < pivot1) { // a[great] <= pivot2
  1613.                         a[k] = a[less];
  1614.                         a[less] = a[great];
  1615.                         ++less;
  1616.                     } else { // pivot1 <= a[great] <= pivot2
  1617.                         a[k] = a[great];
  1618.                     }
  1619.                     /* * Here and below we use "a[i] = b; i--;" instead * of "a[i--] = b;" due to performance issue. */
  1620.                     a[great] = ak;
  1621.                     --great;
  1622.                 }
  1623.             }
  1625.             // Swap pivots into their final positions
  1626.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  1627.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  1629.             // Sort left and right parts recursively, excluding known pivots
  1630.             sort(a, left, less - 2, leftmost);
  1631.             sort(a, great + 2, right, false);
  1633.             /* * If center part is too large (comprises > 4/7 of the array), * swap internal pivot values to ends. */
  1634.             if (less < e1 && e5 < great) {
  1635.                 /* * Skip elements, which are equal to pivot values. */
  1636.                 while (a[less] == pivot1) {
  1637.                     ++less;
  1638.                 }
  1640.                 while (a[great] == pivot2) {
  1641.                     --great;
  1642.                 }
  1644.                 /* * Partitioning: * * left part center part right part * +----------------------------------------------------------+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | * +----------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (*, less) == pivot1 * pivot1 < all in [less, k) < pivot2 * all in (great, *) == pivot2 * * Pointer k is the first index of ?-part. */
  1645.                 outer:
  1646.                 for (int k = less - 1; ++k <= great; ) {
  1647.                     float ak = a[k];
  1648.                     if (ak == pivot1) { // Move a[k] to left part
  1649.                         a[k] = a[less];
  1650.                         a[less] = ak;
  1651.                         ++less;
  1652.                     } else if (ak == pivot2) { // Move a[k] to right part
  1653.                         while (a[great] == pivot2) {
  1654.                             if (great-- == k) {
  1655.                                 break outer;
  1656.                             }
  1657.                         }
  1658.                         if (a[great] == pivot1) { // a[great] < pivot2
  1659.                             a[k] = a[less];
  1660.                             /* * Even though a[great] equals to pivot1, the * assignment a[less] = pivot1 may be incorrect, * if a[great] and pivot1 are floating-point zeros * of different signs. Therefore in float and * double sorting methods we have to use more * accurate assignment a[less] = a[great]. */
  1661.                             a[less] = a[great];
  1662.                             ++less;
  1663.                         } else { // pivot1 < a[great] < pivot2
  1664.                             a[k] = a[great];
  1665.                         }
  1666.                         a[great] = ak;
  1667.                         --great;
  1668.                     }
  1669.                 }
  1670.             }
  1672.             // Sort center part recursively
  1673.             sort(a, less, great, false);
  1675.         } else { // Partitioning with one pivot
  1676.             /* * Use the third of the five sorted elements as pivot. * This value is inexpensive approximation of the median. */
  1677.             float pivot = a[e3];
  1679.             /* * Partitioning degenerates to the traditional 3-way * (or "Dutch National Flag") schema: * * left part center part right part * +-------------------------------------------------+ * | < pivot | == pivot | ? | > pivot | * +-------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot * all in [less, k) == pivot * all in (great, right) > pivot * * Pointer k is the first index of ?-part. */
  1680.             for (int k = less; k <= great; ++k) {
  1681.                 if (a[k] == pivot) {
  1682.                     continue;
  1683.                 }
  1684.                 float ak = a[k];
  1685.                 if (ak < pivot) { // Move a[k] to left part
  1686.                     a[k] = a[less];
  1687.                     a[less] = ak;
  1688.                     ++less;
  1689.                 } else { // a[k] > pivot - Move a[k] to right part
  1690.                     while (a[great] > pivot) {
  1691.                         --great;
  1692.                     }
  1693.                     if (a[great] < pivot) { // a[great] <= pivot
  1694.                         a[k] = a[less];
  1695.                         a[less] = a[great];
  1696.                         ++less;
  1697.                     } else { // a[great] == pivot
  1698.                         /* * Even though a[great] equals to pivot, the * assignment a[k] = pivot may be incorrect, * if a[great] and pivot are floating-point * zeros of different signs. Therefore in float * and double sorting methods we have to use * more accurate assignment a[k] = a[great]. */
  1699.                         a[k] = a[great];
  1700.                     }
  1701.                     a[great] = ak;
  1702.                     --great;
  1703.                 }
  1704.             }
  1706.             /* * Sort left and right parts recursively. * All elements from center part are equal * and, therefore, already sorted. */
  1707.             sort(a, left, less - 1, leftmost);
  1708.             sort(a, great + 1, right, false);
  1709.         }
  1710.     }
  1712.     /** * Sorts the specified range of the array using the given * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  1713.     static void sort(double[] a, int left, int right,
  1714.                      double[] work, int workBase, int workLen) {
  1715.         /* * Phase 1: Move NaNs to the end of the array. */
  1716.         while (left <= right && Double.isNaN(a[right])) {
  1717.             --right;
  1718.         }
  1719.         for (int k = right; --k >= left; ) {
  1720.             double ak = a[k];
  1721.             if (ak != ak) { // a[k] is NaN
  1722.                 a[k] = a[right];
  1723.                 a[right] = ak;
  1724.                 --right;
  1725.             }
  1726.         }
  1728.         /* * Phase 2: Sort everything except NaNs (which are already in place). */
  1729.         doSort(a, left, right, work, workBase, workLen);
  1731.         /* * Phase 3: Place negative zeros before positive zeros. */
  1732.         int hi = right;
  1734.         /* * Find the first zero, or first positive, or last negative element. */
  1735.         while (left < hi) {
  1736.             int middle = (left + hi) >>> 1;
  1737.             double middleValue = a[middle];
  1739.             if (middleValue < 0.0d) {
  1740.                 left = middle + 1;
  1741.             } else {
  1742.                 hi = middle;
  1743.             }
  1744.         }
  1746.         /* * Skip the last negative value (if any) or all leading negative zeros. */
  1747.         while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
  1748.             ++left;
  1749.         }
  1751.         /* * Move negative zeros to the beginning of the sub-range. * * Partitioning: * * +----------------------------------------------------+ * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) | * +----------------------------------------------------+ * ^ ^ ^ * | | | * left p k * * Invariants: * * all in (*, left) < 0.0 * all in [left, p) == -0.0 * all in [p, k) == 0.0 * all in [k, right] >= 0.0 * * Pointer k is the first index of ?-part. */
  1752.         for (int k = left, p = left - 1; ++k <= right; ) {
  1753.             double ak = a[k];
  1754.             if (ak != 0.0d) {
  1755.                 break;
  1756.             }
  1757.             if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
  1758.                 a[k] = 0.0d;
  1759.                 a[++p] = -0.0d;
  1760.             }
  1761.         }
  1762.     }
  1764.     /** * Sorts the specified range of the array. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */
  1765.     private static void doSort(double[] a, int left, int right,
  1766.                                double[] work, int workBase, int workLen) {
  1767.         // Use Quicksort on small arrays
  1768.         if (right - left < QUICKSORT_THRESHOLD) {
  1769.             sort(a, left, right, true);
  1770.             return;
  1771.         }
  1773.         /* * Index run[i] is the start of i-th run * (ascending or descending sequence). */
  1774.         int[] run = new int[MAX_RUN_COUNT + 1];
  1775.         int count = 0; run[0] = left;
  1777.         // Check if the array is nearly sorted
  1778.         for (int k = left; k < right; run[count] = k) {
  1779.             if (a[k] < a[k + 1]) { // ascending
  1780.                 while (++k <= right && a[k - 1] <= a[k]);
  1781.             } else if (a[k] > a[k + 1]) { // descending
  1782.                 while (++k <= right && a[k - 1] >= a[k]);
  1783.                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  1784.                     double t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  1785.                 }
  1786.             } else { // equal
  1787.                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  1788.                     if (--m == 0) {
  1789.                         sort(a, left, right, true);
  1790.                         return;
  1791.                     }
  1792.                 }
  1793.             }
  1795.             /* * The array is not highly structured, * use Quicksort instead of merge sort. */
  1796.             if (++count == MAX_RUN_COUNT) {
  1797.                 sort(a, left, right, true);
  1798.                 return;
  1799.             }
  1800.         }
  1802.         // Check special cases
  1803.         // Implementation note: variable "right" is increased by 1.
  1804.         if (run[count] == right++) { // The last run contains one element
  1805.             run[++count] = right;
  1806.         } else if (count == 1) { // The array is already sorted
  1807.             return;
  1808.         }
  1810.         // Determine alternation base for merge
  1811.         byte odd = 0;
  1812.         for (int n = 1; (n <<= 1) < count; odd ^= 1);
  1814.         // Use or create temporary array b for merging
  1815.         double[] b;                 // temp array; alternates with a
  1816.         int ao, bo;              // array offsets from 'left'
  1817.         int blen = right - left; // space needed for b
  1818.         if (work == null || workLen < blen || workBase + blen > work.length) {
  1819.             work = new double[blen];
  1820.             workBase = 0;
  1821.         }
  1822.         if (odd == 0) {
  1823.             System.arraycopy(a, left, work, workBase, blen);
  1824.             b = a;
  1825.             bo = 0;
  1826.             a = work;
  1827.             ao = workBase - left;
  1828.         } else {
  1829.             b = work;
  1830.             ao = 0;
  1831.             bo = workBase - left;
  1832.         }
  1834.         // Merging
  1835.         for (int last; count > 1; count = last) {
  1836.             for (int k = (last = 0) + 2; k <= count; k += 2) {
  1837.                 int hi = run[k], mi = run[k - 1];
  1838.                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
  1839.                     if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
  1840.                         b[i + bo] = a[p++ + ao];
  1841.                     } else {
  1842.                         b[i + bo] = a[q++ + ao];
  1843.                     }
  1844.                 }
  1845.                 run[++last] = hi;
  1846.             }
  1847.             if ((count & 1) != 0) {
  1848.                 for (int i = right, lo = run[count - 1]; --i >= lo;
  1849.                     b[i + bo] = a[i + ao]
  1850.                 );
  1851.                 run[++last] = right;
  1852.             }
  1853.             double[] t = a; a = b; b = t;
  1854.             int o = ao; ao = bo; bo = o;
  1855.         }
  1856.     }
  1858.     /** * Sorts the specified range of the array by Dual-Pivot Quicksort. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param leftmost indicates if this part is the leftmost in the range */
  1859.     private static void sort(double[] a, int left, int right, boolean leftmost) {
  1860.         int length = right - left + 1;
  1862.         // Use insertion sort on tiny arrays
  1863.         if (length < INSERTION_SORT_THRESHOLD) {
  1864.             if (leftmost) {
  1865.                 /* * Traditional (without sentinel) insertion sort, * optimized for server VM, is used in case of * the leftmost part. */
  1866.                 for (int i = left, j = i; i < right; j = ++i) {
  1867.                     double ai = a[i + 1];
  1868.                     while (ai < a[j]) {
  1869.                         a[j + 1] = a[j];
  1870.                         if (j-- == left) {
  1871.                             break;
  1872.                         }
  1873.                     }
  1874.                     a[j + 1] = ai;
  1875.                 }
  1876.             } else {
  1877.                 /* * Skip the longest ascending sequence. */
  1878.                 do {
  1879.                     if (left >= right) {
  1880.                         return;
  1881.                     }
  1882.                 } while (a[++left] >= a[left - 1]);
  1884.                 /* * Every element from adjoining part plays the role * of sentinel, therefore this allows us to avoid the * left range check on each iteration. Moreover, we use * the more optimized algorithm, so called pair insertion * sort, which is faster (in the context of Quicksort) * than traditional implementation of insertion sort. */
  1885.                 for (int k = left; ++left <= right; k = ++left) {
  1886.                     double a1 = a[k], a2 = a[left];
  1888.                     if (a1 < a2) {
  1889.                         a2 = a1; a1 = a[left];
  1890.                     }
  1891.                     while (a1 < a[--k]) {
  1892.                         a[k + 2] = a[k];
  1893.                     }
  1894.                     a[++k + 1] = a1;
  1896.                     while (a2 < a[--k]) {
  1897.                         a[k + 1] = a[k];
  1898.                     }
  1899.                     a[k + 1] = a2;
  1900.                 }
  1901.                 double last = a[right];
  1903.                 while (last < a[--right]) {
  1904.                     a[right + 1] = a[right];
  1905.                 }
  1906.                 a[right + 1] = last;
  1907.             }
  1908.             return;
  1909.         }
  1911.         // Inexpensive approximation of length / 7
  1912.         int seventh = (length >> 3) + (length >> 6) + 1;
  1914.         /* * Sort five evenly spaced elements around (and including) the * center element in the range. These elements will be used for * pivot selection as described below. The choice for spacing * these elements was empirically determined to work well on * a wide variety of inputs. */
  1915.         int e3 = (left + right) >>> 1; // The midpoint
  1916.         int e2 = e3 - seventh;
  1917.         int e1 = e2 - seventh;
  1918.         int e4 = e3 + seventh;
  1919.         int e5 = e4 + seventh;
  1921.         // Sort these elements using insertion sort
  1922.         if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  1924.         if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  1925.             if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  1926.         }
  1927.         if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  1928.             if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  1929.                 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  1930.             }
  1931.         }
  1932.         if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  1933.             if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  1934.                 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  1935.                     if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  1936.                 }
  1937.             }
  1938.         }
  1940.         // Pointers
  1941.         int less  = left;  // The index of the first element of center part
  1942.         int great = right; // The index before the first element of right part
  1944.         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  1945.             /* * Use the second and fourth of the five sorted elements as pivots. * These values are inexpensive approximations of the first and * second terciles of the array. Note that pivot1 <= pivot2. */
  1946.             double pivot1 = a[e2];
  1947.             double pivot2 = a[e4];
  1949.             /* * The first and the last elements to be sorted are moved to the * locations formerly occupied by the pivots. When partitioning * is complete, the pivots are swapped back into their final * positions, and excluded from subsequent sorting. */
  1950.             a[e2] = a[left];
  1951.             a[e4] = a[right];
  1953.             /* * Skip elements, which are less or greater than pivot values. */
  1954.             while (a[++less] < pivot1);
  1955.             while (a[--great] > pivot2);
  1957.             /* * Partitioning: * * left part center part right part * +--------------------------------------------------------------+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | * +--------------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot1 * pivot1 <= all in [less, k) <= pivot2 * all in (great, right) > pivot2 * * Pointer k is the first index of ?-part. */
  1958.             outer:
  1959.             for (int k = less - 1; ++k <= great; ) {
  1960.                 double ak = a[k];
  1961.                 if (ak < pivot1) { // Move a[k] to left part
  1962.                     a[k] = a[less];
  1963.                     /* * Here and below we use "a[i] = b; i++;" instead * of "a[i++] = b;" due to performance issue. */
  1964.                     a[less] = ak;
  1965.                     ++less;
  1966.                 } else if (ak > pivot2) { // Move a[k] to right part
  1967.                     while (a[great] > pivot2) {
  1968.                         if (great-- == k) {
  1969.                             break outer;
  1970.                         }
  1971.                     }
  1972.                     if (a[great] < pivot1) { // a[great] <= pivot2
  1973.                         a[k] = a[less];
  1974.                         a[less] = a[great];
  1975.                         ++less;
  1976.                     } else { // pivot1 <= a[great] <= pivot2
  1977.                         a[k] = a[great];
  1978.                     }
  1979.                     /* * Here and below we use "a[i] = b; i--;" instead * of "a[i--] = b;" due to performance issue. */
  1980.                     a[great] = ak;
  1981.                     --great;
  1982.                 }
  1983.             }
  1985.             // Swap pivots into their final positions
  1986.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  1987.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  1989.             // Sort left and right parts recursively, excluding known pivots
  1990.             sort(a, left, less - 2, leftmost);
  1991.             sort(a, great + 2, right, false);
  1993.             /* * If center part is too large (comprises > 4/7 of the array), * swap internal pivot values to ends. */
  1994.             if (less < e1 && e5 < great) {
  1995.                 /* * Skip elements, which are equal to pivot values. */
  1996.                 while (a[less] == pivot1) {
  1997.                     ++less;
  1998.                 }
  2000.                 while (a[great] == pivot2) {
  2001.                     --great;
  2002.                 }
  2004.                 /* * Partitioning: * * left part center part right part * +----------------------------------------------------------+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | * +----------------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (*, less) == pivot1 * pivot1 < all in [less, k) < pivot2 * all in (great, *) == pivot2 * * Pointer k is the first index of ?-part. */
  2005.                 outer:
  2006.                 for (int k = less - 1; ++k <= great; ) {
  2007.                     double ak = a[k];
  2008.                     if (ak == pivot1) { // Move a[k] to left part
  2009.                         a[k] = a[less];
  2010.                         a[less] = ak;
  2011.                         ++less;
  2012.                     } else if (ak == pivot2) { // Move a[k] to right part
  2013.                         while (a[great] == pivot2) {
  2014.                             if (great-- == k) {
  2015.                                 break outer;
  2016.                             }
  2017.                         }
  2018.                         if (a[great] == pivot1) { // a[great] < pivot2
  2019.                             a[k] = a[less];
  2020.                             /* * Even though a[great] equals to pivot1, the * assignment a[less] = pivot1 may be incorrect, * if a[great] and pivot1 are floating-point zeros * of different signs. Therefore in float and * double sorting methods we have to use more * accurate assignment a[less] = a[great]. */
  2021.                             a[less] = a[great];
  2022.                             ++less;
  2023.                         } else { // pivot1 < a[great] < pivot2
  2024.                             a[k] = a[great];
  2025.                         }
  2026.                         a[great] = ak;
  2027.                         --great;
  2028.                     }
  2029.                 }
  2030.             }
  2032.             // Sort center part recursively
  2033.             sort(a, less, great, false);
  2035.         } else { // Partitioning with one pivot
  2036.             /* * Use the third of the five sorted elements as pivot. * This value is inexpensive approximation of the median. */
  2037.             double pivot = a[e3];
  2039.             /* * Partitioning degenerates to the traditional 3-way * (or "Dutch National Flag") schema: * * left part center part right part * +-------------------------------------------------+ * | < pivot | == pivot | ? | > pivot | * +-------------------------------------------------+ * ^ ^ ^ * | | | * less k great * * Invariants: * * all in (left, less) < pivot * all in [less, k) == pivot * all in (great, right) > pivot * * Pointer k is the first index of ?-part. */
  2040.             for (int k = less; k <= great; ++k) {
  2041.                 if (a[k] == pivot) {
  2042.                     continue;
  2043.                 }
  2044.                 double ak = a[k];
  2045.                 if (ak < pivot) { // Move a[k] to left part
  2046.                     a[k] = a[less];
  2047.                     a[less] = ak;
  2048.                     ++less;
  2049.                 } else { // a[k] > pivot - Move a[k] to right part
  2050.                     while (a[great] > pivot) {
  2051.                         --great;
  2052.                     }
  2053.                     if (a[great] < pivot) { // a[great] <= pivot
  2054.                         a[k] = a[less];
  2055.                         a[less] = a[great];
  2056.                         ++less;
  2057.                     } else { // a[great] == pivot
  2058.                         /* * Even though a[great] equals to pivot, the * assignment a[k] = pivot may be incorrect, * if a[great] and pivot are floating-point * zeros of different signs. Therefore in float * and double sorting methods we have to use * more accurate assignment a[k] = a[great]. */
  2059.                         a[k] = a[great];
  2060.                     }
  2061.                     a[great] = ak;
  2062.                     --great;
  2063.                 }
  2064.             }
  2066.             /* * Sort left and right parts recursively. * All elements from center part are equal * and, therefore, already sorted. */
  2067.             sort(a, left, less - 1, leftmost);
  2068.             sort(a, great + 1, right, false);
  2069.         }
  2070.     }
  2071. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_43598687/article/details/122209141

内容来源于网络，如有侵权，请联系作者删除！

源码java源码双轴快速排序

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com