# HG changeset patch # User asaha # Date 1256832366 25200 # Node ID df190e90b500d03a511a1a5614250e9f6edce35f # Parent 57dfac1c5aa1d88cc1b8853de9dc71a65f53c866# Parent a94a6faf44e6edd98ceaa88da44946ccf487dc27 Merge diff -r 57dfac1c5aa1 -r df190e90b500 jdk/make/java/java/FILES_java.gmk --- a/jdk/make/java/java/FILES_java.gmk Wed Oct 28 15:47:55 2009 -0700 +++ b/jdk/make/java/java/FILES_java.gmk Thu Oct 29 09:06:06 2009 -0700 @@ -251,6 +251,7 @@ java/util/IdentityHashMap.java \ java/util/EnumMap.java \ java/util/Arrays.java \ + java/util/DualPivotQuicksort.java \ java/util/TimSort.java \ java/util/ComparableTimSort.java \ java/util/ConcurrentModificationException.java \ diff -r 57dfac1c5aa1 -r df190e90b500 jdk/src/share/classes/java/util/Arrays.java --- a/jdk/src/share/classes/java/util/Arrays.java Wed Oct 28 15:47:55 2009 -0700 +++ b/jdk/src/share/classes/java/util/Arrays.java Thu Oct 29 09:06:06 2009 -0700 @@ -1,5 +1,5 @@ /* - * Copyright 1997-2008 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 1997-2009 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -29,1047 +29,458 @@ /** * This class contains various methods for manipulating arrays (such as - * sorting and searching). This class also contains a static factory + * sorting and searching). This class also contains a static factory * that allows arrays to be viewed as lists. * - *

The methods in this class all throw a NullPointerException if - * the specified array reference is null, except where noted. + *

The methods in this class all throw a {@code NullPointerException}, + * if the specified array reference is null, except where noted. * *

The documentation for the methods contained in this class includes - * briefs description of the implementations. Such descriptions should + * briefs description of the implementations. Such descriptions should * be regarded as implementation notes, rather than parts of the - * specification. Implementors should feel free to substitute other - * algorithms, so long as the specification itself is adhered to. (For - * example, the algorithm used by sort(Object[]) does not have to be - * a mergesort, but it does have to be stable.) + * specification. Implementors should feel free to substitute other + * algorithms, so long as the specification itself is adhered to. (For + * example, the algorithm used by {@code sort(Object[])} does not have to be + * a MergeSort, but it does have to be stable.) * *

This class is a member of the * * Java Collections Framework. * - * @author Josh Bloch - * @author Neal Gafter - * @author John Rose - * @since 1.2 + * @author Josh Bloch + * @author Neal Gafter + * @author John Rose + * @since 1.2 */ +public class Arrays { -public class Arrays { // Suppresses default constructor, ensuring non-instantiability. - private Arrays() { - } + private Arrays() {} // Sorting /** - * Sorts the specified array of longs into ascending numerical order. - * The sorting algorithm is a tuned quicksort, adapted from Jon - * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", - * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November - * 1993). This algorithm offers n*log(n) performance on many data sets - * that cause other quicksorts to degrade to quadratic performance. + * Sorts the specified array into ascending numerical order. + * + *

The sorting algorithm is a tuned quicksort, adapted from Jon - * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", - * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November - * 1993). This algorithm offers n*log(n) performance on many data sets - * that cause other quicksorts to degrade to quadratic performance. + *

+ * Sorts the specified range of the specified array into ascending order. The + * range of to be sorted extends from the index {@code fromIndex}, inclusive, + * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, + * the range to be sorted is empty. * - * The sorting algorithm is a tuned quicksort, adapted from Jon - * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", - * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November - * 1993). This algorithm offers n*log(n) performance on many data sets - * that cause other quicksorts to degrade to quadratic performance. + *

- * The < relation does not provide a total order on + * Sorts the specified array into ascending numerical order. + * + *

The {@code <} relation does not provide a total order on * all floating-point values; although they are distinct numbers - * -0.0 == 0.0 is true and a NaN value - * compares neither less than, greater than, nor equal to any - * floating-point value, even itself. To allow the sort to - * proceed, instead of using the < relation to - * determine ascending numerical order, this method uses the total - * order imposed by {@link Double#compareTo}. This ordering - * differs from the < relation in that - * -0.0 is treated as less than 0.0 and - * NaN is considered greater than any other floating-point value. - * For the purposes of sorting, all NaN values are considered - * equivalent and equal. - *

- * The < relation does not provide a total order on - * all floating-point values; although they are distinct numbers - * -0.0 == 0.0 is true and a NaN value - * compares neither less than, greater than, nor equal to any - * floating-point value, even itself. To allow the sort to - * proceed, instead of using the < relation to - * determine ascending numerical order, this method uses the total - * order imposed by {@link Double#compareTo}. This ordering - * differs from the < relation in that - * -0.0 is treated as less than 0.0 and - * NaN is considered greater than any other floating-point value. - * For the purposes of sorting, all NaN values are considered - * equivalent and equal. - *

- * The < relation does not provide a total order on + * Sorts the specified range of the specified array into ascending order. The + * range of to be sorted extends from the index {@code fromIndex}, inclusive, + * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, + * the range to be sorted is empty. + * + *

The {@code <} relation does not provide a total order on * all floating-point values; although they are distinct numbers - * -0.0f == 0.0f is true and a NaN value - * compares neither less than, greater than, nor equal to any - * floating-point value, even itself. To allow the sort to - * proceed, instead of using the < relation to - * determine ascending numerical order, this method uses the total - * order imposed by {@link Float#compareTo}. This ordering - * differs from the < relation in that - * -0.0f is treated as less than 0.0f and - * NaN is considered greater than any other floating-point value. - * For the purposes of sorting, all NaN values are considered - * equivalent and equal. - *

- * The < relation does not provide a total order on - * all floating-point values; although they are distinct numbers - * -0.0f == 0.0f is true and a NaN value - * compares neither less than, greater than, nor equal to any - * floating-point value, even itself. To allow the sort to - * proceed, instead of using the < relation to - * determine ascending numerical order, this method uses the total - * order imposed by {@link Float#compareTo}. This ordering - * differs from the < relation in that - * -0.0f is treated as less than 0.0f and - * NaN is considered greater than any other floating-point value. - * For the purposes of sorting, all NaN values are considered - * equivalent and equal. - *

- * The sorting algorithm is a tuned quicksort, adapted from Jon - * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", - * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November - * 1993). This algorithm offers n*log(n) performance on many data sets - * that cause other quicksorts to degrade to quadratic performance. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element (inclusive) to be - * sorted - * @param toIndex the index of the last element (exclusive) to be sorted - * @throws IllegalArgumentException if fromIndex > toIndex - * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or - * toIndex > a.length - */ - public static void sort(float[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); - sort2(a, fromIndex, toIndex); - } - - private static void sort2(double a[], int fromIndex, int toIndex) { + private static void sortNegZeroAndNaN(double[] a, int fromIndex, int toIndex) { final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d); /* * The sort is done in three phases to avoid the expense of using - * NaN and -0.0 aware comparisons during the main sort. - */ - - /* - * Preprocessing phase: Move any NaN's to end of array, count the - * number of -0.0's, and turn them into 0.0's. + * NaN and -0.0d aware comparisons during the main sort. + * + * Preprocessing phase: move any NaN's to end of array, count the + * number of -0.0d's, and turn them into 0.0d's. */ int numNegZeros = 0; - int i = fromIndex, n = toIndex; - while(i < n) { + int i = fromIndex; + int n = toIndex; + double temp; + + while (i < n) { if (a[i] != a[i]) { - swap(a, i, --n); - } else { - if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) { + n--; + temp = a[i]; + a[i] = a[n]; + a[n] = temp; + } + else { + if (a[i] == 0 && Double.doubleToLongBits(a[i]) == NEG_ZERO_BITS) { a[i] = 0.0d; numNegZeros++; } i++; } } - // Main sort phase: quicksort everything but the NaN's - sort1(a, fromIndex, n-fromIndex); + DualPivotQuicksort.sort(a, fromIndex, n - 1); - // Postprocessing phase: change 0.0's to -0.0's as required + // Postprocessing phase: change 0.0d's to -0.0d's as required if (numNegZeros != 0) { - int j = binarySearch0(a, fromIndex, n, 0.0d); // posn of ANY zero + int j = binarySearch0(a, fromIndex, n, 0.0d); // position of ANY zero + do { j--; - } while (j>=fromIndex && a[j]==0.0d); + } + while (j >= fromIndex && a[j] == 0.0d); // j is now one less than the index of the FIRST zero - for (int k=0; kThe {@code <} relation does not provide a total order on + * all floating-point values; although they are distinct numbers + * {@code -0.0f == 0.0f} is {@code true} and a NaN value compares + * neither less than, greater than, nor equal to any floating-point + * value, even itself. To allow the sort to proceed, instead of using + * the {@code <} relation to determine ascending numerical order, + * this method uses the total order imposed by {@link Float#compareTo}. + * This ordering differs from the {@code <} relation in that {@code -0.0f} + * is treated as less than {@code 0.0f} and NaN is considered greater than + * any other floating-point value. For the purposes of sorting, all NaN + * values are considered equivalent and equal. + * + *

The {@code <} relation does not provide a total order on + * all floating-point values; although they are distinct numbers + * {@code -0.0f == 0.0f} is {@code true} and a NaN value compares + * neither less than, greater than, nor equal to any floating-point + * value, even itself. To allow the sort to proceed, instead of using + * the {@code <} relation to determine ascending numerical order, + * this method uses the total order imposed by {@link Float#compareTo}. + * This ordering differs from the {@code <} relation in that {@code -0.0f} + * is treated as less than {@code 0.0f} and NaN is considered greater than + * any other floating-point value. For the purposes of sorting, all NaN + * values are considered equivalent and equal. + * + *

Implementation note: The sorting algorithm is a Dual-Pivot Quicksort, + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This 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. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element, inclusively, to be sorted + * @param toIndex the index of the last element, exclusively, to be sorted + * @throws IllegalArgumentException if {@code fromIndex > toIndex} + * @throws ArrayIndexOutOfBoundsException + * if {@code fromIndex < 0} or {@code toIndex > a.length} + */ + public static void sort(float[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); + sortNegZeroAndNaN(a, fromIndex, toIndex); + } + + private static void sortNegZeroAndNaN(float[] a, int fromIndex, int toIndex) { final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f); /* * The sort is done in three phases to avoid the expense of using - * NaN and -0.0 aware comparisons during the main sort. - */ - - /* - * Preprocessing phase: Move any NaN's to end of array, count the - * number of -0.0's, and turn them into 0.0's. + * NaN and -0.0f aware comparisons during the main sort. + * + * Preprocessing phase: move any NaN's to end of array, count the + * number of -0.0f's, and turn them into 0.0f's. */ int numNegZeros = 0; - int i = fromIndex, n = toIndex; - while(i < n) { + int i = fromIndex; + int n = toIndex; + float temp; + + while (i < n) { if (a[i] != a[i]) { - swap(a, i, --n); - } else { - if (a[i]==0 && Float.floatToIntBits(a[i])==NEG_ZERO_BITS) { + n--; + temp = a[i]; + a[i] = a[n]; + a[n] = temp; + } + else { + if (a[i] == 0 && Float.floatToIntBits(a[i]) == NEG_ZERO_BITS) { a[i] = 0.0f; numNegZeros++; } i++; } } - // Main sort phase: quicksort everything but the NaN's - sort1(a, fromIndex, n-fromIndex); + DualPivotQuicksort.sort(a, fromIndex, n - 1); - // Postprocessing phase: change 0.0's to -0.0's as required + // Postprocessing phase: change 0.0f's to -0.0f's as required if (numNegZeros != 0) { - int j = binarySearch0(a, fromIndex, n, 0.0f); // posn of ANY zero + int j = binarySearch0(a, fromIndex, n, 0.0f); // position of ANY zero + do { j--; - } while (j>=fromIndex && a[j]==0.0f); + } + while (j >= fromIndex && a[j] == 0.0f); // j is now one less than the index of the FIRST zero - for (int k=0; koff && x[j-1]>x[j]; j--) - swap(x, j, j-1); - return; - } - - // Choose a partition element, v - int m = off + (len >> 1); // Small arrays, middle element - if (len > 7) { - int l = off; - int n = off + len - 1; - if (len > 40) { // Big arrays, pseudomedian of 9 - int s = len/8; - l = med3(x, l, l+s, l+2*s); - m = med3(x, m-s, m, m+s); - n = med3(x, n-2*s, n-s, n); - } - m = med3(x, l, m, n); // Mid-size, med of 3 - } - long v = x[m]; - - // Establish Invariant: v* (v)* v* - int a = off, b = a, c = off + len - 1, d = c; - while(true) { - while (b <= c && x[b] <= v) { - if (x[b] == v) - swap(x, a++, b); - b++; - } - while (c >= b && x[c] >= v) { - if (x[c] == v) - swap(x, c, d--); - c--; - } - if (b > c) - break; - swap(x, b++, c--); - } - - // Swap partition elements back to middle - int s, n = off + len; - s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); - s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); - - // Recursively sort non-partition-elements - if ((s = b-a) > 1) - sort1(x, off, s); - if ((s = d-c) > 1) - sort1(x, n-s, s); - } - - /** - * Swaps x[a] with x[b]. - */ - private static void swap(long x[], int a, int b) { - long t = x[a]; - x[a] = x[b]; - x[b] = t; - } - - /** - * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. - */ - private static void vecswap(long x[], int a, int b, int n) { - for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); - } - - /** - * Sorts the specified sub-array of integers into ascending order. - */ - private static void sort1(int x[], int off, int len) { - // Insertion sort on smallest arrays - if (len < 7) { - for (int i=off; ioff && x[j-1]>x[j]; j--) - swap(x, j, j-1); - return; - } - - // Choose a partition element, v - int m = off + (len >> 1); // Small arrays, middle element - if (len > 7) { - int l = off; - int n = off + len - 1; - if (len > 40) { // Big arrays, pseudomedian of 9 - int s = len/8; - l = med3(x, l, l+s, l+2*s); - m = med3(x, m-s, m, m+s); - n = med3(x, n-2*s, n-s, n); - } - m = med3(x, l, m, n); // Mid-size, med of 3 - } - int v = x[m]; - - // Establish Invariant: v* (v)* v* - int a = off, b = a, c = off + len - 1, d = c; - while(true) { - while (b <= c && x[b] <= v) { - if (x[b] == v) - swap(x, a++, b); - b++; - } - while (c >= b && x[c] >= v) { - if (x[c] == v) - swap(x, c, d--); - c--; - } - if (b > c) - break; - swap(x, b++, c--); - } - - // Swap partition elements back to middle - int s, n = off + len; - s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); - s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); - - // Recursively sort non-partition-elements - if ((s = b-a) > 1) - sort1(x, off, s); - if ((s = d-c) > 1) - sort1(x, n-s, s); - } - - /** - * Swaps x[a] with x[b]. - */ - private static void swap(int x[], int a, int b) { - int t = x[a]; - x[a] = x[b]; - x[b] = t; - } - - /** - * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. - */ - private static void vecswap(int x[], int a, int b, int n) { - for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); - } - - /** - * Sorts the specified sub-array of shorts into ascending order. - */ - private static void sort1(short x[], int off, int len) { - // Insertion sort on smallest arrays - if (len < 7) { - for (int i=off; ioff && x[j-1]>x[j]; j--) - swap(x, j, j-1); - return; - } - - // Choose a partition element, v - int m = off + (len >> 1); // Small arrays, middle element - if (len > 7) { - int l = off; - int n = off + len - 1; - if (len > 40) { // Big arrays, pseudomedian of 9 - int s = len/8; - l = med3(x, l, l+s, l+2*s); - m = med3(x, m-s, m, m+s); - n = med3(x, n-2*s, n-s, n); - } - m = med3(x, l, m, n); // Mid-size, med of 3 - } - short v = x[m]; - - // Establish Invariant: v* (v)* v* - int a = off, b = a, c = off + len - 1, d = c; - while(true) { - while (b <= c && x[b] <= v) { - if (x[b] == v) - swap(x, a++, b); - b++; - } - while (c >= b && x[c] >= v) { - if (x[c] == v) - swap(x, c, d--); - c--; - } - if (b > c) - break; - swap(x, b++, c--); - } - - // Swap partition elements back to middle - int s, n = off + len; - s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); - s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); - - // Recursively sort non-partition-elements - if ((s = b-a) > 1) - sort1(x, off, s); - if ((s = d-c) > 1) - sort1(x, n-s, s); - } - - /** - * Swaps x[a] with x[b]. - */ - private static void swap(short x[], int a, int b) { - short t = x[a]; - x[a] = x[b]; - x[b] = t; - } - - /** - * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. - */ - private static void vecswap(short x[], int a, int b, int n) { - for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); - } - - - /** - * Sorts the specified sub-array of chars into ascending order. - */ - private static void sort1(char x[], int off, int len) { - // Insertion sort on smallest arrays - if (len < 7) { - for (int i=off; ioff && x[j-1]>x[j]; j--) - swap(x, j, j-1); - return; - } - - // Choose a partition element, v - int m = off + (len >> 1); // Small arrays, middle element - if (len > 7) { - int l = off; - int n = off + len - 1; - if (len > 40) { // Big arrays, pseudomedian of 9 - int s = len/8; - l = med3(x, l, l+s, l+2*s); - m = med3(x, m-s, m, m+s); - n = med3(x, n-2*s, n-s, n); - } - m = med3(x, l, m, n); // Mid-size, med of 3 - } - char v = x[m]; - - // Establish Invariant: v* (v)* v* - int a = off, b = a, c = off + len - 1, d = c; - while(true) { - while (b <= c && x[b] <= v) { - if (x[b] == v) - swap(x, a++, b); - b++; } - while (c >= b && x[c] >= v) { - if (x[c] == v) - swap(x, c, d--); - c--; - } - if (b > c) - break; - swap(x, b++, c--); } - - // Swap partition elements back to middle - int s, n = off + len; - s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); - s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); - - // Recursively sort non-partition-elements - if ((s = b-a) > 1) - sort1(x, off, s); - if ((s = d-c) > 1) - sort1(x, n-s, s); - } - - /** - * Swaps x[a] with x[b]. - */ - private static void swap(char x[], int a, int b) { - char t = x[a]; - x[a] = x[b]; - x[b] = t; - } - - /** - * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. - */ - private static void vecswap(char x[], int a, int b, int n) { - for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); - } - - - /** - * Sorts the specified sub-array of bytes into ascending order. - */ - private static void sort1(byte x[], int off, int len) { - // Insertion sort on smallest arrays - if (len < 7) { - for (int i=off; ioff && x[j-1]>x[j]; j--) - swap(x, j, j-1); - return; - } - - // Choose a partition element, v - int m = off + (len >> 1); // Small arrays, middle element - if (len > 7) { - int l = off; - int n = off + len - 1; - if (len > 40) { // Big arrays, pseudomedian of 9 - int s = len/8; - l = med3(x, l, l+s, l+2*s); - m = med3(x, m-s, m, m+s); - n = med3(x, n-2*s, n-s, n); - } - m = med3(x, l, m, n); // Mid-size, med of 3 - } - byte v = x[m]; - - // Establish Invariant: v* (v)* v* - int a = off, b = a, c = off + len - 1, d = c; - while(true) { - while (b <= c && x[b] <= v) { - if (x[b] == v) - swap(x, a++, b); - b++; - } - while (c >= b && x[c] >= v) { - if (x[c] == v) - swap(x, c, d--); - c--; - } - if (b > c) - break; - swap(x, b++, c--); - } - - // Swap partition elements back to middle - int s, n = off + len; - s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); - s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); - - // Recursively sort non-partition-elements - if ((s = b-a) > 1) - sort1(x, off, s); - if ((s = d-c) > 1) - sort1(x, n-s, s); - } - - /** - * Swaps x[a] with x[b]. - */ - private static void swap(byte x[], int a, int b) { - byte t = x[a]; - x[a] = x[b]; - x[b] = t; - } - - /** - * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. - */ - private static void vecswap(byte x[], int a, int b, int n) { - for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); - } - - - /** - * Sorts the specified sub-array of doubles into ascending order. - */ - private static void sort1(double x[], int off, int len) { - // Insertion sort on smallest arrays - if (len < 7) { - for (int i=off; ioff && x[j-1]>x[j]; j--) - swap(x, j, j-1); - return; - } - - // Choose a partition element, v - int m = off + (len >> 1); // Small arrays, middle element - if (len > 7) { - int l = off; - int n = off + len - 1; - if (len > 40) { // Big arrays, pseudomedian of 9 - int s = len/8; - l = med3(x, l, l+s, l+2*s); - m = med3(x, m-s, m, m+s); - n = med3(x, n-2*s, n-s, n); - } - m = med3(x, l, m, n); // Mid-size, med of 3 - } - double v = x[m]; - - // Establish Invariant: v* (v)* v* - int a = off, b = a, c = off + len - 1, d = c; - while(true) { - while (b <= c && x[b] <= v) { - if (x[b] == v) - swap(x, a++, b); - b++; - } - while (c >= b && x[c] >= v) { - if (x[c] == v) - swap(x, c, d--); - c--; - } - if (b > c) - break; - swap(x, b++, c--); - } - - // Swap partition elements back to middle - int s, n = off + len; - s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); - s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); - - // Recursively sort non-partition-elements - if ((s = b-a) > 1) - sort1(x, off, s); - if ((s = d-c) > 1) - sort1(x, n-s, s); - } - - /** - * Swaps x[a] with x[b]. - */ - private static void swap(double x[], int a, int b) { - double t = x[a]; - x[a] = x[b]; - x[b] = t; - } - - /** - * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. - */ - private static void vecswap(double x[], int a, int b, int n) { - for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); - } - - - /** - * Sorts the specified sub-array of floats into ascending order. - */ - private static void sort1(float x[], int off, int len) { - // Insertion sort on smallest arrays - if (len < 7) { - for (int i=off; ioff && x[j-1]>x[j]; j--) - swap(x, j, j-1); - return; - } - - // Choose a partition element, v - int m = off + (len >> 1); // Small arrays, middle element - if (len > 7) { - int l = off; - int n = off + len - 1; - if (len > 40) { // Big arrays, pseudomedian of 9 - int s = len/8; - l = med3(x, l, l+s, l+2*s); - m = med3(x, m-s, m, m+s); - n = med3(x, n-2*s, n-s, n); - } - m = med3(x, l, m, n); // Mid-size, med of 3 - } - float v = x[m]; - - // Establish Invariant: v* (v)* v* - int a = off, b = a, c = off + len - 1, d = c; - while(true) { - while (b <= c && x[b] <= v) { - if (x[b] == v) - swap(x, a++, b); - b++; - } - while (c >= b && x[c] >= v) { - if (x[c] == v) - swap(x, c, d--); - c--; - } - if (b > c) - break; - swap(x, b++, c--); - } - - // Swap partition elements back to middle - int s, n = off + len; - s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); - s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); - - // Recursively sort non-partition-elements - if ((s = b-a) > 1) - sort1(x, off, s); - if ((s = d-c) > 1) - sort1(x, n-s, s); - } - - /** - * Swaps x[a] with x[b]. - */ - private static void swap(float x[], int a, int b) { - float t = x[a]; - x[a] = x[b]; - x[b] = t; - } - - /** - * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. - */ - private static void vecswap(float x[], int a, int b, int n) { - for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); } /** * Old merge sort implementation can be selected (for * compatibility with broken comparators) using a system property. * Cannot be a static boolean in the enclosing class due to - * circular dependencies. To be removed in a future release. + * circular dependencies. To be removed in a future release. */ static final class LegacyMergeSort { private static final boolean userRequested = @@ -1235,7 +646,7 @@ /** * Tuning parameter: list size at or below which insertion sort will be - * used in preference to mergesort or quicksort. + * used in preference to mergesort. * To be removed in a future release. */ private static final int INSERTIONSORT_THRESHOLD = 7; @@ -1474,17 +885,20 @@ } /** - * Check that fromIndex and toIndex are in range, and throw an - * appropriate exception if they aren't. + * Checks that {@code fromIndex} and {@code toIndex} are in + * the range and throws an appropriate exception, if they aren't. */ - private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) { - if (fromIndex > toIndex) - throw new IllegalArgumentException("fromIndex(" + fromIndex + - ") > toIndex(" + toIndex+")"); - if (fromIndex < 0) + private static void rangeCheck(int length, int fromIndex, int toIndex) { + if (fromIndex > toIndex) { + throw new IllegalArgumentException( + "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); + } + if (fromIndex < 0) { throw new ArrayIndexOutOfBoundsException(fromIndex); - if (toIndex > arrayLen) + } + if (toIndex > length) { throw new ArrayIndexOutOfBoundsException(toIndex); + } } // Searching @@ -1987,21 +1401,21 @@ /** * Searches the specified array of floats for the specified value using - * the binary search algorithm. The array must be sorted - * (as by the {@link #sort(float[])} method) prior to making this call. If - * it is not sorted, the results are undefined. If the array contains + * the binary search algorithm. The array must be sorted + * (as by the {@link #sort(float[])} method) prior to making this call. If + * it is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which - * one will be found. This method considers all NaN values to be + * one will be found. This method considers all NaN values to be * equivalent and equal. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; - * otherwise, (-(insertion point) - 1). The + * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all - * elements in the array are less than the specified key. Note + * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. */ @@ -2015,10 +1429,10 @@ * the binary search algorithm. * The range must be sorted * (as by the {@link #sort(float[], int, int)} method) - * prior to making this call. If - * it is not sorted, the results are undefined. If the range contains + * prior to making this call. If + * it is not sorted, the results are undefined. If the range contains * multiple elements with the specified value, there is no guarantee which - * one will be found. This method considers all NaN values to be + * one will be found. This method considers all NaN values to be * equivalent and equal. * * @param a the array to be searched @@ -2028,12 +1442,12 @@ * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; - * otherwise, (-(insertion point) - 1). The + * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all - * elements in the range are less than the specified key. Note + * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws IllegalArgumentException @@ -2076,10 +1490,9 @@ return -(low + 1); // key not found. } - /** * Searches the specified array for the specified object using the binary - * search algorithm. The array must be sorted into ascending order + * search algorithm. The array must be sorted into ascending order * according to the * {@linkplain Comparable natural ordering} * of its elements (as by the @@ -2269,7 +1682,6 @@ int mid = (low + high) >>> 1; T midVal = a[mid]; int cmp = c.compare(midVal, key); - if (cmp < 0) low = mid + 1; else if (cmp > 0) @@ -2280,7 +1692,6 @@ return -(low + 1); // key not found. } - // Equality Testing /** @@ -2527,7 +1938,6 @@ return true; } - /** * Returns true if the two specified arrays of Objects are * equal to one another. The two arrays are considered equal if @@ -2562,7 +1972,6 @@ return true; } - // Filling /** @@ -2885,8 +2294,8 @@ a[i] = val; } + // Cloning - // Cloning /** * Copies the specified array, truncating or padding with nulls (if necessary) * so the copy has the specified length. For all indices that are @@ -3495,7 +2904,6 @@ return copy; } - // Misc /** @@ -4180,6 +3588,7 @@ public static String toString(float[] a) { if (a == null) return "null"; + int iMax = a.length - 1; if (iMax == -1) return "[]"; @@ -4243,6 +3652,7 @@ public static String toString(Object[] a) { if (a == null) return "null"; + int iMax = a.length - 1; if (iMax == -1) return "[]"; diff -r 57dfac1c5aa1 -r df190e90b500 jdk/src/share/classes/java/util/DualPivotQuicksort.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/java/util/DualPivotQuicksort.java Thu Oct 29 09:06:06 2009 -0700 @@ -0,0 +1,1554 @@ +/* + * Copyright 2009 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + */ + +package java.util; + +/** + * This class implements the Dual-Pivot Quicksort algorithm by + * Vladimir Yaroslavskiy, Jon Bentley, and Joshua 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. + * + * @author Vladimir Yaroslavskiy + * @author Jon Bentley + * @author Josh Bloch + * + * @version 2009.10.22 m765.827.v4 + */ +final class DualPivotQuicksort { + + // Suppresses default constructor, ensuring non-instantiability. + private DualPivotQuicksort() {} + + /* + * Tuning Parameters. + */ + + /** + * If the length of an array to be sorted is less than this + * constant, insertion sort is used in preference to Quicksort. + */ + private static final int INSERTION_SORT_THRESHOLD = 32; + + /** + * If the length of a byte array to be sorted is greater than + * this constant, counting sort is used in preference to Quicksort. + */ + private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 128; + + /** + * 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. + */ + private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768; + + /* + * Sorting methods for the seven primitive types. + */ + + /** + * Sorts the specified range of the array into ascending order. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + static void sort(int[] a, int left, int right) { + // Use insertion sort on tiny arrays + if (right - left + 1 < INSERTION_SORT_THRESHOLD) { + for (int k = left + 1; k <= right; k++) { + int ak = a[k]; + int j; + + for (j = k - 1; j >= left && ak < a[j]; j--) { + a[j + 1] = a[j]; + } + a[j + 1] = ak; + } + } else { // Use Dual-Pivot Quicksort on large arrays + dualPivotQuicksort(a, left, right); + } + } + + /** + * Sorts the specified range of the array into ascending order + * by Dual-Pivot Quicksort. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + private static void dualPivotQuicksort(int[] a, int left, int right) { + // Compute indices of five evenly spaced elements + int sixth = (right - left + 1) / 6; + int e1 = left + sixth; + int e5 = right - sixth; + int e3 = (left + right) >>> 1; // The midpoint + int e4 = e3 + sixth; + int e2 = e3 - sixth; + + // Sort these elements in place using a 5-element sorting network + if (a[e1] > a[e2]) { int t = a[e1]; a[e1] = a[e2]; a[e2] = t; } + if (a[e4] > a[e5]) { int t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + if (a[e1] > a[e3]) { int t = a[e1]; a[e1] = a[e3]; a[e3] = t; } + if (a[e2] > a[e3]) { int t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e1] > a[e4]) { int t = a[e1]; a[e1] = a[e4]; a[e4] = t; } + if (a[e3] > a[e4]) { int t = a[e3]; a[e3] = a[e4]; a[e4] = t; } + if (a[e2] > a[e5]) { int t = a[e2]; a[e2] = a[e5]; a[e5] = t; } + if (a[e2] > a[e3]) { int t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e4] > a[e5]) { int t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + + /* + * 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. + * + * The pivots are stored in local variables, and the first and + * the last of the sorted elements 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. + */ + int pivot1 = a[e2]; a[e2] = a[left]; + int pivot2 = a[e4]; a[e4] = a[right]; + + /* + * Partitioning + * + * left part center part right part + * ------------------------------------------------------------ + * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] + * ------------------------------------------------------------ + * ^ ^ ^ + * | | | + * less k great + */ + + // Pointers + int less = left + 1; // The index of first element of center part + int great = right - 1; // The index before first element of right part + + boolean pivotsDiffer = pivot1 != pivot2; + + if (pivotsDiffer) { + /* + * 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 + */ + for (int k = less; k <= great; k++) { + int ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else if (ak > pivot2) { + while (a[great] > pivot2 && k < great) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } else { // Pivots are equal + /* + * Partition degenerates to the traditional 3-way + * (or "Dutch National Flag") partition: + * + * 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 + */ + for (int k = less; k <= great; k++) { + int ak = a[k]; + + if (ak == pivot1) { + continue; + } + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else { + while (a[great] > pivot1) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } + + // Swap pivots into their final positions + a[left] = a[less - 1]; a[less - 1] = pivot1; + a[right] = a[great + 1]; a[great + 1] = pivot2; + + // Sort left and right parts recursively, excluding known pivot values + sort(a, left, less - 2); + sort(a, great + 2, right); + + /* + * If pivot1 == pivot2, all elements from center + * part are equal and, therefore, already sorted + */ + if (!pivotsDiffer) { + return; + } + + /* + * If center part is too large (comprises > 5/6 of + * the array), swap internal pivot values to ends + */ + if (less < e1 && e5 < great) { + while (a[less] == pivot1) { + less++; + } + for (int k = less + 1; k <= great; k++) { + if (a[k] == pivot1) { + a[k] = a[less]; + a[less++] = pivot1; + } + } + while (a[great] == pivot2) { + great--; + } + for (int k = great - 1; k >= less; k--) { + if (a[k] == pivot2) { + a[k] = a[great]; + a[great--] = pivot2; + } + } + } + + // Sort center part recursively, excluding known pivot values + sort(a, less, great); + } + + /** + * Sorts the specified range of the array into ascending order. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + static void sort(long[] a, int left, int right) { + // Use insertion sort on tiny arrays + if (right - left + 1 < INSERTION_SORT_THRESHOLD) { + for (int k = left + 1; k <= right; k++) { + long ak = a[k]; + int j; + + for (j = k - 1; j >= left && ak < a[j]; j--) { + a[j + 1] = a[j]; + } + a[j + 1] = ak; + } + } else { // Use Dual-Pivot Quicksort on large arrays + dualPivotQuicksort(a, left, right); + } + } + + /** + * Sorts the specified range of the array into ascending order + * by Dual-Pivot Quicksort. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + private static void dualPivotQuicksort(long[] a, int left, int right) { + // Compute indices of five evenly spaced elements + int sixth = (right - left + 1) / 6; + int e1 = left + sixth; + int e5 = right - sixth; + int e3 = (left + right) >>> 1; // The midpoint + int e4 = e3 + sixth; + int e2 = e3 - sixth; + + // Sort these elements in place using a 5-element sorting network + if (a[e1] > a[e2]) { long t = a[e1]; a[e1] = a[e2]; a[e2] = t; } + if (a[e4] > a[e5]) { long t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + if (a[e1] > a[e3]) { long t = a[e1]; a[e1] = a[e3]; a[e3] = t; } + if (a[e2] > a[e3]) { long t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e1] > a[e4]) { long t = a[e1]; a[e1] = a[e4]; a[e4] = t; } + if (a[e3] > a[e4]) { long t = a[e3]; a[e3] = a[e4]; a[e4] = t; } + if (a[e2] > a[e5]) { long t = a[e2]; a[e2] = a[e5]; a[e5] = t; } + if (a[e2] > a[e3]) { long t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e4] > a[e5]) { long t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + + /* + * 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. + * + * The pivots are stored in local variables, and the first and + * the last of the sorted elements 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. + */ + long pivot1 = a[e2]; a[e2] = a[left]; + long pivot2 = a[e4]; a[e4] = a[right]; + + /* + * Partitioning + * + * left part center part right part + * ------------------------------------------------------------ + * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] + * ------------------------------------------------------------ + * ^ ^ ^ + * | | | + * less k great + */ + + // Pointers + int less = left + 1; // The index of first element of center part + int great = right - 1; // The index before first element of right part + + boolean pivotsDiffer = pivot1 != pivot2; + + if (pivotsDiffer) { + /* + * 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 + */ + for (int k = less; k <= great; k++) { + long ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else if (ak > pivot2) { + while (a[great] > pivot2 && k < great) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } else { // Pivots are equal + /* + * Partition degenerates to the traditional 3-way + * (or "Dutch National Flag") partition: + * + * 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 + */ + for (int k = less; k <= great; k++) { + long ak = a[k]; + + if (ak == pivot1) { + continue; + } + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else { + while (a[great] > pivot1) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } + + // Swap pivots into their final positions + a[left] = a[less - 1]; a[less - 1] = pivot1; + a[right] = a[great + 1]; a[great + 1] = pivot2; + + // Sort left and right parts recursively, excluding known pivot values + sort(a, left, less - 2); + sort(a, great + 2, right); + + /* + * If pivot1 == pivot2, all elements from center + * part are equal and, therefore, already sorted + */ + if (!pivotsDiffer) { + return; + } + + /* + * If center part is too large (comprises > 5/6 of + * the array), swap internal pivot values to ends + */ + if (less < e1 && e5 < great) { + while (a[less] == pivot1) { + less++; + } + for (int k = less + 1; k <= great; k++) { + if (a[k] == pivot1) { + a[k] = a[less]; + a[less++] = pivot1; + } + } + while (a[great] == pivot2) { + great--; + } + for (int k = great - 1; k >= less; k--) { + if (a[k] == pivot2) { + a[k] = a[great]; + a[great--] = pivot2; + } + } + } else { // Use Dual-Pivot Quicksort on large arrays + dualPivotQuicksort(a, left, right); + } + } + + /** The number of distinct short values */ + private static final int NUM_SHORT_VALUES = 1 << 16; + + /** + * Sorts the specified range of the array into ascending order. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + static void sort(short[] a, int left, int right) { + // Use insertion sort on tiny arrays + if (right - left + 1 < INSERTION_SORT_THRESHOLD) { + for (int k = left + 1; k <= right; k++) { + short ak = a[k]; + int j; + + for (j = k - 1; j >= left && ak < a[j]; j--) { + a[j + 1] = a[j]; + } + a[j + 1] = ak; + } + } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { + // Use counting sort on huge arrays + int[] count = new int[NUM_SHORT_VALUES]; + + for (int i = left; i <= right; i++) { + count[a[i] - Short.MIN_VALUE]++; + } + for (int i = 0, k = left; i < count.length && k < right; i++) { + short value = (short) (i + Short.MIN_VALUE); + + for (int s = count[i]; s > 0; s--) { + a[k++] = value; + } + } + } else { // Use Dual-Pivot Quicksort on large arrays + dualPivotQuicksort(a, left, right); + } + } + + /** + * Sorts the specified range of the array into ascending order + * by Dual-Pivot Quicksort. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + private static void dualPivotQuicksort(short[] a, int left, int right) { + // Compute indices of five evenly spaced elements + int sixth = (right - left + 1) / 6; + int e1 = left + sixth; + int e5 = right - sixth; + int e3 = (left + right) >>> 1; // The midpoint + int e4 = e3 + sixth; + int e2 = e3 - sixth; + + // Sort these elements in place using a 5-element sorting network + if (a[e1] > a[e2]) { short t = a[e1]; a[e1] = a[e2]; a[e2] = t; } + if (a[e4] > a[e5]) { short t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + if (a[e1] > a[e3]) { short t = a[e1]; a[e1] = a[e3]; a[e3] = t; } + if (a[e2] > a[e3]) { short t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e1] > a[e4]) { short t = a[e1]; a[e1] = a[e4]; a[e4] = t; } + if (a[e3] > a[e4]) { short t = a[e3]; a[e3] = a[e4]; a[e4] = t; } + if (a[e2] > a[e5]) { short t = a[e2]; a[e2] = a[e5]; a[e5] = t; } + if (a[e2] > a[e3]) { short t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e4] > a[e5]) { short t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + + /* + * 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. + * + * The pivots are stored in local variables, and the first and + * the last of the sorted elements 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. + */ + short pivot1 = a[e2]; a[e2] = a[left]; + short pivot2 = a[e4]; a[e4] = a[right]; + + /* + * Partitioning + * + * left part center part right part + * ------------------------------------------------------------ + * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] + * ------------------------------------------------------------ + * ^ ^ ^ + * | | | + * less k great + */ + + // Pointers + int less = left + 1; // The index of first element of center part + int great = right - 1; // The index before first element of right part + + boolean pivotsDiffer = pivot1 != pivot2; + + if (pivotsDiffer) { + /* + * 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 + */ + for (int k = less; k <= great; k++) { + short ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else if (ak > pivot2) { + while (a[great] > pivot2 && k < great) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } else { // Pivots are equal + /* + * Partition degenerates to the traditional 3-way + * (or "Dutch National Flag") partition: + * + * 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 + */ + for (int k = less; k <= great; k++) { + short ak = a[k]; + + if (ak == pivot1) { + continue; + } + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else { + while (a[great] > pivot1) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } + + // Swap pivots into their final positions + a[left] = a[less - 1]; a[less - 1] = pivot1; + a[right] = a[great + 1]; a[great + 1] = pivot2; + + // Sort left and right parts recursively, excluding known pivot values + sort(a, left, less - 2); + sort(a, great + 2, right); + + /* + * If pivot1 == pivot2, all elements from center + * part are equal and, therefore, already sorted + */ + if (!pivotsDiffer) { + return; + } + + /* + * If center part is too large (comprises > 5/6 of + * the array), swap internal pivot values to ends + */ + if (less < e1 && e5 < great) { + while (a[less] == pivot1) { + less++; + } + for (int k = less + 1; k <= great; k++) { + if (a[k] == pivot1) { + a[k] = a[less]; + a[less++] = pivot1; + } + } + while (a[great] == pivot2) { + great--; + } + for (int k = great - 1; k >= less; k--) { + if (a[k] == pivot2) { + a[k] = a[great]; + a[great--] = pivot2; + } + } + } + + // Sort center part recursively, excluding known pivot values + sort(a, less, great); + } + + /** The number of distinct byte values */ + private static final int NUM_BYTE_VALUES = 1 << 8; + + /** + * Sorts the specified range of the array into ascending order. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + static void sort(byte[] a, int left, int right) { + // Use insertion sort on tiny arrays + if (right - left + 1 < INSERTION_SORT_THRESHOLD) { + for (int k = left + 1; k <= right; k++) { + byte ak = a[k]; + int j; + + for (j = k - 1; j >= left && ak < a[j]; j--) { + a[j + 1] = a[j]; + } + a[j + 1] = ak; + } + } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) { + // Use counting sort on large arrays + int[] count = new int[NUM_BYTE_VALUES]; + + for (int i = left; i <= right; i++) { + count[a[i] - Byte.MIN_VALUE]++; + } + for (int i = 0, k = left; i < count.length && k < right; i++) { + byte value = (byte) (i + Byte.MIN_VALUE); + + for (int s = count[i]; s > 0; s--) { + a[k++] = value; + } + } + } else { // Use Dual-Pivot Quicksort on large arrays + dualPivotQuicksort(a, left, right); + } + } + + /** + * Sorts the specified range of the array into ascending order + * by Dual-Pivot Quicksort. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + private static void dualPivotQuicksort(byte[] a, int left, int right) { + // Compute indices of five evenly spaced elements + int sixth = (right - left + 1) / 6; + int e1 = left + sixth; + int e5 = right - sixth; + int e3 = (left + right) >>> 1; // The midpoint + int e4 = e3 + sixth; + int e2 = e3 - sixth; + + // Sort these elements in place using a 5-element sorting network + if (a[e1] > a[e2]) { byte t = a[e1]; a[e1] = a[e2]; a[e2] = t; } + if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + if (a[e1] > a[e3]) { byte t = a[e1]; a[e1] = a[e3]; a[e3] = t; } + if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e1] > a[e4]) { byte t = a[e1]; a[e1] = a[e4]; a[e4] = t; } + if (a[e3] > a[e4]) { byte t = a[e3]; a[e3] = a[e4]; a[e4] = t; } + if (a[e2] > a[e5]) { byte t = a[e2]; a[e2] = a[e5]; a[e5] = t; } + if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + + /* + * 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. + * + * The pivots are stored in local variables, and the first and + * the last of the sorted elements 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. + */ + byte pivot1 = a[e2]; a[e2] = a[left]; + byte pivot2 = a[e4]; a[e4] = a[right]; + + /* + * Partitioning + * + * left part center part right part + * ------------------------------------------------------------ + * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] + * ------------------------------------------------------------ + * ^ ^ ^ + * | | | + * less k great + */ + + // Pointers + int less = left + 1; // The index of first element of center part + int great = right - 1; // The index before first element of right part + + boolean pivotsDiffer = pivot1 != pivot2; + + if (pivotsDiffer) { + /* + * 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 + */ + for (int k = less; k <= great; k++) { + byte ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else if (ak > pivot2) { + while (a[great] > pivot2 && k < great) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } else { // Pivots are equal + /* + * Partition degenerates to the traditional 3-way + * (or "Dutch National Flag") partition: + * + * 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 + */ + for (int k = less; k <= great; k++) { + byte ak = a[k]; + + if (ak == pivot1) { + continue; + } + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else { + while (a[great] > pivot1) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } + + // Swap pivots into their final positions + a[left] = a[less - 1]; a[less - 1] = pivot1; + a[right] = a[great + 1]; a[great + 1] = pivot2; + + // Sort left and right parts recursively, excluding known pivot values + sort(a, left, less - 2); + sort(a, great + 2, right); + + /* + * If pivot1 == pivot2, all elements from center + * part are equal and, therefore, already sorted + */ + if (!pivotsDiffer) { + return; + } + + /* + * If center part is too large (comprises > 5/6 of + * the array), swap internal pivot values to ends + */ + if (less < e1 && e5 < great) { + while (a[less] == pivot1) { + less++; + } + for (int k = less + 1; k <= great; k++) { + if (a[k] == pivot1) { + a[k] = a[less]; + a[less++] = pivot1; + } + } + while (a[great] == pivot2) { + great--; + } + for (int k = great - 1; k >= less; k--) { + if (a[k] == pivot2) { + a[k] = a[great]; + a[great--] = pivot2; + } + } + } + + // Sort center part recursively, excluding known pivot values + sort(a, less, great); + } + + /** The number of distinct char values */ + private static final int NUM_CHAR_VALUES = 1 << 16; + + /** + * Sorts the specified range of the array into ascending order. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + static void sort(char[] a, int left, int right) { + // Use insertion sort on tiny arrays + if (right - left + 1 < INSERTION_SORT_THRESHOLD) { + for (int k = left + 1; k <= right; k++) { + char ak = a[k]; + int j; + + for (j = k - 1; j >= left && ak < a[j]; j--) { + a[j + 1] = a[j]; + } + a[j + 1] = ak; + } + } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { + // Use counting sort on huge arrays + int[] count = new int[NUM_CHAR_VALUES]; + + for (int i = left; i <= right; i++) { + count[a[i]]++; + } + for (int i = 0, k = left; i < count.length && k < right; i++) { + for (int s = count[i]; s > 0; s--) { + a[k++] = (char) i; + } + } + } else { // Use Dual-Pivot Quicksort on large arrays + dualPivotQuicksort(a, left, right); + } + } + + /** + * Sorts the specified range of the array into ascending order + * by Dual-Pivot Quicksort. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + private static void dualPivotQuicksort(char[] a, int left, int right) { + // Compute indices of five evenly spaced elements + int sixth = (right - left + 1) / 6; + int e1 = left + sixth; + int e5 = right - sixth; + int e3 = (left + right) >>> 1; // The midpoint + int e4 = e3 + sixth; + int e2 = e3 - sixth; + + // Sort these elements in place using a 5-element sorting network + if (a[e1] > a[e2]) { char t = a[e1]; a[e1] = a[e2]; a[e2] = t; } + if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + if (a[e1] > a[e3]) { char t = a[e1]; a[e1] = a[e3]; a[e3] = t; } + if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e1] > a[e4]) { char t = a[e1]; a[e1] = a[e4]; a[e4] = t; } + if (a[e3] > a[e4]) { char t = a[e3]; a[e3] = a[e4]; a[e4] = t; } + if (a[e2] > a[e5]) { char t = a[e2]; a[e2] = a[e5]; a[e5] = t; } + if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + + /* + * 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. + * + * The pivots are stored in local variables, and the first and + * the last of the sorted elements 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. + */ + char pivot1 = a[e2]; a[e2] = a[left]; + char pivot2 = a[e4]; a[e4] = a[right]; + + /* + * Partitioning + * + * left part center part right part + * ------------------------------------------------------------ + * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] + * ------------------------------------------------------------ + * ^ ^ ^ + * | | | + * less k great + */ + + // Pointers + int less = left + 1; // The index of first element of center part + int great = right - 1; // The index before first element of right part + + boolean pivotsDiffer = pivot1 != pivot2; + + if (pivotsDiffer) { + /* + * 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 + */ + for (int k = less; k <= great; k++) { + char ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else if (ak > pivot2) { + while (a[great] > pivot2 && k < great) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } else { // Pivots are equal + /* + * Partition degenerates to the traditional 3-way + * (or "Dutch National Flag") partition: + * + * 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 + */ + for (int k = less; k <= great; k++) { + char ak = a[k]; + + if (ak == pivot1) { + continue; + } + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else { + while (a[great] > pivot1) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } + + // Swap pivots into their final positions + a[left] = a[less - 1]; a[less - 1] = pivot1; + a[right] = a[great + 1]; a[great + 1] = pivot2; + + // Sort left and right parts recursively, excluding known pivot values + sort(a, left, less - 2); + sort(a, great + 2, right); + + /* + * If pivot1 == pivot2, all elements from center + * part are equal and, therefore, already sorted + */ + if (!pivotsDiffer) { + return; + } + + /* + * If center part is too large (comprises > 5/6 of + * the array), swap internal pivot values to ends + */ + if (less < e1 && e5 < great) { + while (a[less] == pivot1) { + less++; + } + for (int k = less + 1; k <= great; k++) { + if (a[k] == pivot1) { + a[k] = a[less]; + a[less++] = pivot1; + } + } + while (a[great] == pivot2) { + great--; + } + for (int k = great - 1; k >= less; k--) { + if (a[k] == pivot2) { + a[k] = a[great]; + a[great--] = pivot2; + } + } + } + + // Sort center part recursively, excluding known pivot values + sort(a, less, great); + } + + /** + * Sorts the specified range of the array into ascending order. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + static void sort(float[] a, int left, int right) { + // Use insertion sort on tiny arrays + if (right - left + 1 < INSERTION_SORT_THRESHOLD) { + for (int k = left + 1; k <= right; k++) { + float ak = a[k]; + int j; + + for (j = k - 1; j >= left && ak < a[j]; j--) { + a[j + 1] = a[j]; + } + a[j + 1] = ak; + } + } else { // Use Dual-Pivot Quicksort on large arrays + dualPivotQuicksort(a, left, right); + } + } + + /** + * Sorts the specified range of the array into ascending order + * by Dual-Pivot Quicksort. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + private static void dualPivotQuicksort(float[] a, int left, int right) { + // Compute indices of five evenly spaced elements + int sixth = (right - left + 1) / 6; + int e1 = left + sixth; + int e5 = right - sixth; + int e3 = (left + right) >>> 1; // The midpoint + int e4 = e3 + sixth; + int e2 = e3 - sixth; + + // Sort these elements in place using a 5-element sorting network + if (a[e1] > a[e2]) { float t = a[e1]; a[e1] = a[e2]; a[e2] = t; } + if (a[e4] > a[e5]) { float t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + if (a[e1] > a[e3]) { float t = a[e1]; a[e1] = a[e3]; a[e3] = t; } + if (a[e2] > a[e3]) { float t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e1] > a[e4]) { float t = a[e1]; a[e1] = a[e4]; a[e4] = t; } + if (a[e3] > a[e4]) { float t = a[e3]; a[e3] = a[e4]; a[e4] = t; } + if (a[e2] > a[e5]) { float t = a[e2]; a[e2] = a[e5]; a[e5] = t; } + if (a[e2] > a[e3]) { float t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e4] > a[e5]) { float t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + + /* + * 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. + * + * The pivots are stored in local variables, and the first and + * the last of the sorted elements 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. + */ + float pivot1 = a[e2]; a[e2] = a[left]; + float pivot2 = a[e4]; a[e4] = a[right]; + + /* + * Partitioning + * + * left part center part right part + * ------------------------------------------------------------ + * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] + * ------------------------------------------------------------ + * ^ ^ ^ + * | | | + * less k great + */ + + // Pointers + int less = left + 1; // The index of first element of center part + int great = right - 1; // The index before first element of right part + + boolean pivotsDiffer = pivot1 != pivot2; + + if (pivotsDiffer) { + /* + * 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 + */ + for (int k = less; k <= great; k++) { + float ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else if (ak > pivot2) { + while (a[great] > pivot2 && k < great) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } else { // Pivots are equal + /* + * Partition degenerates to the traditional 3-way + * (or "Dutch National Flag") partition: + * + * 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 + */ + for (int k = less; k <= great; k++) { + float ak = a[k]; + + if (ak == pivot1) { + continue; + } + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else { + while (a[great] > pivot1) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } + + // Swap pivots into their final positions + a[left] = a[less - 1]; a[less - 1] = pivot1; + a[right] = a[great + 1]; a[great + 1] = pivot2; + + // Sort left and right parts recursively, excluding known pivot values + sort(a, left, less - 2); + sort(a, great + 2, right); + + /* + * If pivot1 == pivot2, all elements from center + * part are equal and, therefore, already sorted + */ + if (!pivotsDiffer) { + return; + } + + /* + * If center part is too large (comprises > 5/6 of + * the array), swap internal pivot values to ends + */ + if (less < e1 && e5 < great) { + while (a[less] == pivot1) { + less++; + } + for (int k = less + 1; k <= great; k++) { + if (a[k] == pivot1) { + a[k] = a[less]; + a[less++] = pivot1; + } + } + while (a[great] == pivot2) { + great--; + } + for (int k = great - 1; k >= less; k--) { + if (a[k] == pivot2) { + a[k] = a[great]; + a[great--] = pivot2; + } + } + } + + // Sort center part recursively, excluding known pivot values + sort(a, less, great); + } + + /** + * Sorts the specified range of the array into ascending order. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + static void sort(double[] a, int left, int right) { + // Use insertion sort on tiny arrays + if (right - left + 1 < INSERTION_SORT_THRESHOLD) { + for (int k = left + 1; k <= right; k++) { + double ak = a[k]; + int j; + + for (j = k - 1; j >= left && ak < a[j]; j--) { + a[j + 1] = a[j]; + } + a[j + 1] = ak; + } + } else { // Use Dual-Pivot Quicksort on large arrays + dualPivotQuicksort(a, left, right); + } + } + + /** + * Sorts the specified range of the array into ascending order + * by Dual-Pivot Quicksort. + * + * @param a the array to be sorted + * @param left the index of the first element, inclusively, to be sorted + * @param right the index of the last element, inclusively, to be sorted + */ + private static void dualPivotQuicksort(double[] a, int left, int right) { + // Compute indices of five evenly spaced elements + int sixth = (right - left + 1) / 6; + int e1 = left + sixth; + int e5 = right - sixth; + int e3 = (left + right) >>> 1; // The midpoint + int e4 = e3 + sixth; + int e2 = e3 - sixth; + + // Sort these elements in place using a 5-element sorting network + if (a[e1] > a[e2]) { double t = a[e1]; a[e1] = a[e2]; a[e2] = t; } + if (a[e4] > a[e5]) { double t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + if (a[e1] > a[e3]) { double t = a[e1]; a[e1] = a[e3]; a[e3] = t; } + if (a[e2] > a[e3]) { double t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e1] > a[e4]) { double t = a[e1]; a[e1] = a[e4]; a[e4] = t; } + if (a[e3] > a[e4]) { double t = a[e3]; a[e3] = a[e4]; a[e4] = t; } + if (a[e2] > a[e5]) { double t = a[e2]; a[e2] = a[e5]; a[e5] = t; } + if (a[e2] > a[e3]) { double t = a[e2]; a[e2] = a[e3]; a[e3] = t; } + if (a[e4] > a[e5]) { double t = a[e4]; a[e4] = a[e5]; a[e5] = t; } + + /* + * 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. + * + * The pivots are stored in local variables, and the first and + * the last of the sorted elements 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. + */ + double pivot1 = a[e2]; a[e2] = a[left]; + double pivot2 = a[e4]; a[e4] = a[right]; + + /* + * Partitioning + * + * left part center part right part + * ------------------------------------------------------------ + * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] + * ------------------------------------------------------------ + * ^ ^ ^ + * | | | + * less k great + */ + + // Pointers + int less = left + 1; // The index of first element of center part + int great = right - 1; // The index before first element of right part + + boolean pivotsDiffer = pivot1 != pivot2; + + if (pivotsDiffer) { + /* + * 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 + */ + for (int k = less; k <= great; k++) { + double ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else if (ak > pivot2) { + while (a[great] > pivot2 && k < great) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } else { // Pivots are equal + /* + * Partition degenerates to the traditional 3-way + * (or "Dutch National Flag") partition: + * + * 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 + */ + for (int k = less; k <= great; k++) { + double ak = a[k]; + + if (ak == pivot1) { + continue; + } + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } else { + while (a[great] > pivot1) { + great--; + } + a[k] = a[great]; + a[great--] = ak; + ak = a[k]; + + if (ak < pivot1) { + a[k] = a[less]; + a[less++] = ak; + } + } + } + } + + // Swap pivots into their final positions + a[left] = a[less - 1]; a[less - 1] = pivot1; + a[right] = a[great + 1]; a[great + 1] = pivot2; + + // Sort left and right parts recursively, excluding known pivot values + sort(a, left, less - 2); + sort(a, great + 2, right); + + /* + * If pivot1 == pivot2, all elements from center + * part are equal and, therefore, already sorted + */ + if (!pivotsDiffer) { + return; + } + + /* + * If center part is too large (comprises > 5/6 of + * the array), swap internal pivot values to ends + */ + if (less < e1 && e5 < great) { + while (a[less] == pivot1) { + less++; + } + for (int k = less + 1; k <= great; k++) { + if (a[k] == pivot1) { + a[k] = a[less]; + a[less++] = pivot1; + } + } + while (a[great] == pivot2) { + great--; + } + for (int k = great - 1; k >= less; k--) { + if (a[k] == pivot2) { + a[k] = a[great]; + a[great--] = pivot2; + } + } + } + + // Sort center part recursively, excluding known pivot values + sort(a, less, great); + } +}