IBM JDK

  1. public static void sort(int[] a) {
  2.     boolean sortWasSuccessfulOnGPU = tryIntSortOnGPU(a);
  3.     if (sortWasSuccessfulOnGPU) {
  4.         return;
  5.     } else {
  6.         DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
  7.     }
  8. }
  9. public static void sort(int[] a, int fromIndex, int toIndex) {
  10.     rangeCheck(a.length, fromIndex, toIndex);
  11.     DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
  12. }
  13. public static void sort(long[] a, int fromIndex, int toIndex) {
  14.     rangeCheck(a.length, fromIndex, toIndex);
  15.     DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
  16. }
  17. public static void sort(short[] a) {
  18.     DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
  19. }
  20. public static void sort(short[] a, int fromIndex, int toIndex) {
  21.     rangeCheck(a.length, fromIndex, toIndex);
  22.     DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
  23. }
  24. public static void sort(char[] a) {
  25.     DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
  26. }
  27. public static void sort(char[] a, int fromIndex, int toIndex) {
  28.     rangeCheck(a.length, fromIndex, toIndex);
  29.     DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
  30. }
  31. public static void sort(byte[] a) {
  32.     DualPivotQuicksort.sort(a, 0, a.length - 1);
  33. }
  34. public static void sort(byte[] a, int fromIndex, int toIndex) {
  35.     rangeCheck(a.length, fromIndex, toIndex);
  36.     DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
  37. }
  38. public static void sort(float[] a) {
  39.     boolean sortWasSuccessfulOnGPU = tryFloatSortOnGPU(a);
  40.     if (sortWasSuccessfulOnGPU) {
  41.         return;
  42.     } else {
  43.         DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
  44.     }
  45. }
  46. public static void sort(float[] a, int fromIndex, int toIndex) {
  47.     rangeCheck(a.length, fromIndex, toIndex);
  48.     DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
  49. }
  50. public static void sort(double[] a) {
  51.     boolean sortWasSuccessfulOnGPU = tryDoubleSortOnGPU(a);
  52.     if (sortWasSuccessfulOnGPU) {
  53.         return;
  54.     } else {
  55.         DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
  56.     }
  57. }
  58. public static void sort(double[] a, int fromIndex, int toIndex) {
  59.     rangeCheck(a.length, fromIndex, toIndex);
  60.     DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
  61. }
  62. public static void sort(Object[] a) {
  63.     if (LegacyMergeSort.userRequested)
  64.         legacyMergeSort(a);
  65.     else
  66.         ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
  67. }
  68. public static void sort(Object[] a, int fromIndex, int toIndex) {
  69.     rangeCheck(a.length, fromIndex, toIndex);
  70.     if (LegacyMergeSort.userRequested)
  71.         legacyMergeSort(a, fromIndex, toIndex);
  72.     else
  73.         ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
  74. }

Oracle JDK

  1. private static void sort(int[] a, int left, int right, boolean leftmost) {
  2.     int length = right - left + 1;
  4.     // Use insertion sort on tiny arrays
  5.     if (length < INSERTION_SORT_THRESHOLD) {
  6.         if (leftmost) {
  7.             /*
  8.              * Traditional (without sentinel) insertion sort,
  9.              * optimized for server VM, is used in case of
  10.              * the leftmost part.
  11.              */
  12.             for (int i = left, j = i; i < right; j = ++i) {
  13.                 int ai = a[i + 1];
  14.                 while (ai < a[j]) {
  15.                     a[j + 1] = a[j];
  16.                     if (j-- == left) {
  17.                         break;
  18.                     }
  19.                 }
  20.                 a[j + 1] = ai;
  21.             }
  22.         } else {
  23.             /*
  24.                  * Skip the longest ascending sequence.
  25.                  */
  26.             do {
  27.                 if (left >= right) {
  28.                     return;
  29.                 }
  30.             } while (a[++left] >= a[left - 1]);
  32.             /*
  33.                  * Every element from adjoining part plays the role
  34.                  * of sentinel, therefore this allows us to avoid the
  35.                  * left range check on each iteration. Moreover, we use
  36.                  * the more optimized algorithm, so called pair insertion
  37.                  * sort, which is faster (in the context of Quicksort)
  38.                  * than traditional implementation of insertion sort.
  39.                  */
  40.             for (int k = left; ++left <= right; k = ++left) {
  41.                 int a1 = a[k], a2 = a[left];
  43.                 if (a1 < a2) {
  44.                     a2 = a1; a1 = a[left];
  45.                 }
  46.                 while (a1 < a[--k]) {
  47.                     a[k + 2] = a[k];
  48.                 }
  49.                 a[++k + 1] = a1;
  51.                 while (a2 < a[--k]) {
  52.                     a[k + 1] = a[k];
  53.                 }
  54.                 a[k + 1] = a2;
  55.             }
  56.             int last = a[right];
  58.             while (last < a[--right]) {
  59.                 a[right + 1] = a[right];
  60.             }
  61.             a[right + 1] = last;
  62.         }
  63.         return;
  64.     }
  66.     // Inexpensive approximation of length / 7
  67.     int seventh = (length >> 3) + (length >> 6) + 1;
  69.     /*
  70.          * Sort five evenly spaced elements around (and including) the
  71.          * center element in the range. These elements will be used for
  72.          * pivot selection as described below. The choice for spacing
  73.          * these elements was empirically determined to work well on
  74.          * a wide variety of inputs.
  75.          */
  76.     int e3 = (left + right) >>> 1; // The midpoint
  77.     int e2 = e3 - seventh;
  78.     int e1 = e2 - seventh;
  79.     int e4 = e3 + seventh;
  80.     int e5 = e4 + seventh;
  82.     // Sort these elements using insertion sort
  83.     if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  85.     if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  86.                         if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  87.                        }
  88.     if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  89.                         if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  90.                                         if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  91.                                        }
  92.                        }
  93.     if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  94.                         if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  95.                                         if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  96.                                                         if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  97.                                                        }
  98.                                        }
  99.                        }
  101.     // Pointers
  102.     int less  = left;  // The index of the first element of center part
  103.     int great = right; // The index before the first element of right part
  105.     if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  106.         /*
  107.              * Use the second and fourth of the five sorted elements as pivots.
  108.              * These values are inexpensive approximations of the first and
  109.              * second terciles of the array. Note that pivot1 <= pivot2.
  110.              */
  111.         int pivot1 = a[e2];
  112.         int pivot2 = a[e4];
  114.         /*
  115.              * The first and the last elements to be sorted are moved to the
  116.              * locations formerly occupied by the pivots. When partitioning
  117.              * is complete, the pivots are swapped back into their final
  118.              * positions, and excluded from subsequent sorting.
  119.              */
  120.         a[e2] = a[left];
  121.         a[e4] = a[right];
  123.         /*
  124.              * Skip elements, which are less or greater than pivot values.
  125.              */
  126.         while (a[++less] < pivot1);
  127.         while (a[--great] > pivot2);
  129.         /*
  130.              * Partitioning:
  131.              *
  132.              *   left part           center part                   right part
  133.              * +--------------------------------------------------------------+
  134.              * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
  135.              * +--------------------------------------------------------------+
  136.              *               ^                          ^       ^
  137.              *               |                          |       |
  138.              *              less                        k     great
  139.              *
  140.              * Invariants:
  141.              *
  142.              *              all in (left, less)   < pivot1
  143.              *    pivot1 <= all in [less, k)     <= pivot2
  144.              *              all in (great, right) > pivot2
  145.              *
  146.              * Pointer k is the first index of ?-part.
  147.              */
  148.         outer:
  149.         for (int k = less - 1; ++k <= great; ) {
  150.             int ak = a[k];
  151.             if (ak < pivot1) { // Move a[k] to left part
  152.                 a[k] = a[less];
  153.                 /*
  154.                      * Here and below we use "a[i] = b; i++;" instead
  155.                      * of "a[i++] = b;" due to performance issue.
  156.                      */
  157.                 a[less] = ak;
  158.                 ++less;
  159.             } else if (ak > pivot2) { // Move a[k] to right part
  160.                 while (a[great] > pivot2) {
  161.                     if (great-- == k) {
  162.                         break outer;
  163.                     }
  164.                 }
  165.                 if (a[great] < pivot1) { // a[great] <= pivot2
  166.                     a[k] = a[less];
  167.                     a[less] = a[great];
  168.                     ++less;
  169.                 } else { // pivot1 <= a[great] <= pivot2
  170.                     a[k] = a[great];
  171.                 }
  172.                 /*
  173.                      * Here and below we use "a[i] = b; i--;" instead
  174.                      * of "a[i--] = b;" due to performance issue.
  175.                      */
  176.                 a[great] = ak;
  177.                 --great;
  178.             }
  179.         }
  181.         // Swap pivots into their final positions
  182.         a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  183.         a[right] = a[great + 1]; a[great + 1] = pivot2;
  185.         // Sort left and right parts recursively, excluding known pivots
  186.         sort(a, left, less - 2, leftmost);
  187.         sort(a, great + 2, right, false);
  189.         /*
  190.              * If center part is too large (comprises > 4/7 of the array),
  191.              * swap internal pivot values to ends.
  192.              */
  193.         if (less < e1 && e5 < great) {
  194.             /*
  195.                  * Skip elements, which are equal to pivot values.
  196.                  */
  197.             while (a[less] == pivot1) {
  198.                 ++less;
  199.             }
  201.             while (a[great] == pivot2) {
  202.                 --great;
  203.             }
  205.             /*
  206.                  * Partitioning:
  207.                  *
  208.                  *   left part         center part                  right part
  209.                  * +----------------------------------------------------------+
  210.                  * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
  211.                  * +----------------------------------------------------------+
  212.                  *              ^                        ^       ^
  213.                  *              |                        |       |
  214.                  *             less                      k     great
  215.                  *
  216.                  * Invariants:
  217.                  *
  218.                  *              all in (*,  less) == pivot1
  219.                  *     pivot1 < all in [less,  k)  < pivot2
  220.                  *              all in (great, *) == pivot2
  221.                  *
  222.                  * Pointer k is the first index of ?-part.
  223.                  */
  224.             outer:
  225.             for (int k = less - 1; ++k <= great; ) {
  226.                 int ak = a[k];
  227.                 if (ak == pivot1) { // Move a[k] to left part
  228.                     a[k] = a[less];
  229.                     a[less] = ak;
  230.                     ++less;
  231.                 } else if (ak == pivot2) { // Move a[k] to right part
  232.                     while (a[great] == pivot2) {
  233.                         if (great-- == k) {
  234.                             break outer;
  235.                         }
  236.                     }
  237.                     if (a[great] == pivot1) { // a[great] < pivot2
  238.                         a[k] = a[less];
  239.                         /*
  240.                              * Even though a[great] equals to pivot1, the
  241.                              * assignment a[less] = pivot1 may be incorrect,
  242.                              * if a[great] and pivot1 are floating-point zeros
  243.                              * of different signs. Therefore in float and
  244.                              * double sorting methods we have to use more
  245.                              * accurate assignment a[less] = a[great].
  246.                              */
  247.                         a[less] = pivot1;
  248.                         ++less;
  249.                     } else { // pivot1 < a[great] < pivot2
  250.                         a[k] = a[great];
  251.                     }
  252.                     a[great] = ak;
  253.                     --great;
  254.                 }
  255.             }
  256.         }
  258.         // Sort center part recursively
  259.         sort(a, less, great, false);
  261.     } else { // Partitioning with one pivot
  262.         /*
  263.              * Use the third of the five sorted elements as pivot.
  264.              * This value is inexpensive approximation of the median.
  265.              */
  266.         int pivot = a[e3];
  268.         /*
  269.              * Partitioning degenerates to the traditional 3-way
  270.              * (or "Dutch National Flag") schema:
  271.              *
  272.              *   left part    center part              right part
  273.              * +-------------------------------------------------+
  274.              * |  < pivot  |   == pivot   |     ?    |  > pivot  |
  275.              * +-------------------------------------------------+
  276.              *              ^              ^        ^
  277.              *              |              |        |
  278.              *             less            k      great
  279.              *
  280.              * Invariants:
  281.              *
  282.              *   all in (left, less)   < pivot
  283.              *   all in [less, k)     == pivot
  284.              *   all in (great, right) > pivot
  285.              *
  286.              * Pointer k is the first index of ?-part.
  287.              */
  288.         for (int k = less; k <= great; ++k) {
  289.             if (a[k] == pivot) {
  290.                 continue;
  291.             }
  292.             int ak = a[k];
  293.             if (ak < pivot) { // Move a[k] to left part
  294.                 a[k] = a[less];
  295.                 a[less] = ak;
  296.                 ++less;
  297.             } else { // a[k] > pivot - Move a[k] to right part
  298.                 while (a[great] > pivot) {
  299.                     --great;
  300.                 }
  301.                 if (a[great] < pivot) { // a[great] <= pivot
  302.                     a[k] = a[less];
  303.                     a[less] = a[great];
  304.                     ++less;
  305.                 } else { // a[great] == pivot
  306.                     /*
  307.                          * Even though a[great] equals to pivot, the
  308.                          * assignment a[k] = pivot may be incorrect,
  309.                          * if a[great] and pivot are floating-point
  310.                          * zeros of different signs. Therefore in float
  311.                          * and double sorting methods we have to use
  312.                          * more accurate assignment a[k] = a[great].
  313.                          */
  314.                     a[k] = pivot;
  315.                 }
  316.                 a[great] = ak;
  317.                 --great;
  318.             }
  319.         }
  321.         /*
  322.              * Sort left and right parts recursively.
  323.              * All elements from center part are equal
  324.              * and, therefore, already sorted.
  325.              */
  326.         sort(a, left, less - 1, leftmost);
  327.         sort(a, great + 1, right, false);
  328.     }
  329. }