changeset 1809:6b3e1ded17e1

Merge
author mchung
date Thu, 29 Oct 2009 19:55:52 -0700
parents 4f8f07be9e7e b05abb410c52
children a1923ebcd61b
files
diffstat 12 files changed, 2138 insertions(+), 916 deletions(-) [+]
line wrap: on
line diff
--- a/make/java/java/FILES_java.gmk	Thu Oct 29 09:22:00 2009 -0700
+++ b/make/java/java/FILES_java.gmk	Thu Oct 29 19:55:52 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 \
--- a/src/share/classes/java/util/Arrays.java	Thu Oct 29 09:22:00 2009 -0700
+++ b/src/share/classes/java/util/Arrays.java	Thu Oct 29 19:55:52 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.
  *
- * <p>The methods in this class all throw a <tt>NullPointerException</tt> if
- * the specified array reference is null, except where noted.
+ * <p>The methods in this class all throw a {@code NullPointerException},
+ * if the specified array reference is null, except where noted.
  *
  * <p>The documentation for the methods contained in this class includes
- * briefs description of the <i>implementations</i>.  Such descriptions should
+ * briefs description of the <i>implementations</i>. Such descriptions should
  * be regarded as <i>implementation notes</i>, rather than parts of the
- * <i>specification</i>.  Implementors should feel free to substitute other
- * algorithms, so long as the specification itself is adhered to.  (For
- * example, the algorithm used by <tt>sort(Object[])</tt> does not have to be
- * a mergesort, but it does have to be <i>stable</i>.)
+ * <i>specification</i>. 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 <i>stable</i>.)
  *
  * <p>This class is a member of the
  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  * Java Collections Framework</a>.
  *
- * @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.
+     *
+     * <p>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
      */
     public static void sort(long[] a) {
-        sort1(a, 0, a.length);
+        sort(a, 0, a.length);
     }
 
     /**
-     * Sorts the specified range of the specified array of longs into
-     * ascending numerical order.  The range to be sorted extends from index
-     * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
-     * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
+     * 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.
      *
-     * <p>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.
+     * <p>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 (inclusive) to be
-     *        sorted
-     * @param toIndex the index of the last element (exclusive) to be sorted
-     * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
-     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
-     * <tt>toIndex &gt; a.length</tt>
+     * @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(long[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        sort1(a, fromIndex, toIndex-fromIndex);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
     }
 
     /**
-     * Sorts the specified array of ints 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.
+     *
+     * <p>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
      */
     public static void sort(int[] a) {
-        sort1(a, 0, a.length);
+        sort(a, 0, a.length);
     }
 
     /**
-     * Sorts the specified range of the specified array of ints into
-     * ascending numerical order.  The range to be sorted extends from index
-     * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
-     * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
+     * 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.
+     * <p>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 (inclusive) to be
-     *        sorted
-     * @param toIndex the index of the last element (exclusive) to be sorted
-     * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
-     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
-     *         <tt>toIndex &gt; a.length</tt>
+     * @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(int[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        sort1(a, fromIndex, toIndex-fromIndex);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
     }
 
     /**
-     * Sorts the specified array of shorts 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.
+     *
+     * <p>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
      */
     public static void sort(short[] a) {
-        sort1(a, 0, a.length);
+        sort(a, 0, a.length);
     }
 
     /**
-     * Sorts the specified range of the specified array of shorts into
-     * ascending numerical order.  The range to be sorted extends from index
-     * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
-     * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
+     * 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.
+     * <p>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 (inclusive) to be
-     *        sorted
-     * @param toIndex the index of the last element (exclusive) to be sorted
-     * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
-     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
-     *         <tt>toIndex &gt; a.length</tt>
+     * @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(short[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        sort1(a, fromIndex, toIndex-fromIndex);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
     }
 
     /**
-     * Sorts the specified array of chars 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.
+     *
+     * <p>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
      */
     public static void sort(char[] a) {
-        sort1(a, 0, a.length);
+        sort(a, 0, a.length);
     }
 
     /**
-     * Sorts the specified range of the specified array of chars into
-     * ascending numerical order.  The range to be sorted extends from index
-     * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
-     * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
+     * 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.
+     * <p>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 (inclusive) to be
-     *        sorted
-     * @param toIndex the index of the last element (exclusive) to be sorted
-     * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
-     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
-     *         <tt>toIndex &gt; a.length</tt>
+     * @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(char[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        sort1(a, fromIndex, toIndex-fromIndex);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
     }
 
     /**
-     * Sorts the specified array of bytes 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.
+     *
+     * <p>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
      */
     public static void sort(byte[] a) {
-        sort1(a, 0, a.length);
+        sort(a, 0, a.length);
     }
 
     /**
-     * Sorts the specified range of the specified array of bytes into
-     * ascending numerical order.  The range to be sorted extends from index
-     * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
-     * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
+     * 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.
+     * <p>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 (inclusive) to be
-     *        sorted
-     * @param toIndex the index of the last element (exclusive) to be sorted
-     * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
-     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
-     *         <tt>toIndex &gt; a.length</tt>
+     * @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(byte[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        sort1(a, fromIndex, toIndex-fromIndex);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
     }
 
     /**
-     * Sorts the specified array of doubles into ascending numerical order.
-     * <p>
-     * The <code>&lt;</code> relation does not provide a total order on
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>The {@code <} relation does not provide a total order on
      * all floating-point values; although they are distinct numbers
-     * <code>-0.0 == 0.0</code> is <code>true</code> 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>&lt;</code> relation to
-     * determine ascending numerical order, this method uses the total
-     * order imposed by {@link Double#compareTo}.  This ordering
-     * differs from the <code>&lt;</code> relation in that
-     * <code>-0.0</code> is treated as less than <code>0.0</code> and
-     * NaN is considered greater than any other floating-point value.
-     * For the purposes of sorting, all NaN values are considered
-     * equivalent and equal.
-     * <p>
-     * 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.
+     * {@code -0.0d == 0.0d} 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 Double#compareTo}.
+     * This ordering differs from the {@code <} relation in that {@code -0.0d}
+     * is treated as less than {@code 0.0d} and NaN is considered greater than
+     * any other floating-point value. For the purposes of sorting, all NaN
+     * values are considered equivalent and equal.
+     *
+     * <p>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
      */
     public static void sort(double[] a) {
-        sort2(a, 0, a.length);
+        sort(a, 0, a.length);
     }
 
     /**
-     * Sorts the specified range of the specified array of doubles into
-     * ascending numerical order.  The range to be sorted extends from index
-     * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
-     * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
-     * <p>
-     * The <code>&lt;</code> 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.
+     *
+     * <p>The {@code <} relation does not provide a total order on
      * all floating-point values; although they are distinct numbers
-     * <code>-0.0 == 0.0</code> is <code>true</code> 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>&lt;</code> relation to
-     * determine ascending numerical order, this method uses the total
-     * order imposed by {@link Double#compareTo}.  This ordering
-     * differs from the <code>&lt;</code> relation in that
-     * <code>-0.0</code> is treated as less than <code>0.0</code> and
-     * NaN is considered greater than any other floating-point value.
-     * For the purposes of sorting, all NaN values are considered
-     * equivalent and equal.
-     * <p>
-     * 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.
+     * {@code -0.0d == 0.0d} 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 Double#compareTo}.
+     * This ordering differs from the {@code <} relation in that {@code -0.0d}
+     * is treated as less than {@code 0.0d} and NaN is considered greater than
+     * any other floating-point value. For the purposes of sorting, all NaN
+     * values are considered equivalent and equal.
+     *
+     * <p>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 (inclusive) to be
-     *        sorted
-     * @param toIndex the index of the last element (exclusive) to be sorted
-     * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
-     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
-     *         <tt>toIndex &gt; a.length</tt>
+     * @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(double[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        sort2(a, fromIndex, toIndex);
+        sortNegZeroAndNaN(a, fromIndex, toIndex);
     }
 
-    /**
-     * Sorts the specified array of floats into ascending numerical order.
-     * <p>
-     * The <code>&lt;</code> relation does not provide a total order on
-     * all floating-point values; although they are distinct numbers
-     * <code>-0.0f == 0.0f</code> is <code>true</code> 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>&lt;</code> relation to
-     * determine ascending numerical order, this method uses the total
-     * order imposed by {@link Float#compareTo}.  This ordering
-     * differs from the <code>&lt;</code> relation in that
-     * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
-     * NaN is considered greater than any other floating-point value.
-     * For the purposes of sorting, all NaN values are considered
-     * equivalent and equal.
-     * <p>
-     * 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
-     */
-    public static void sort(float[] a) {
-        sort2(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the specified array of floats into
-     * ascending numerical order.  The range to be sorted extends from index
-     * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
-     * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
-     * <p>
-     * The <code>&lt;</code> relation does not provide a total order on
-     * all floating-point values; although they are distinct numbers
-     * <code>-0.0f == 0.0f</code> is <code>true</code> 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>&lt;</code> relation to
-     * determine ascending numerical order, this method uses the total
-     * order imposed by {@link Float#compareTo}.  This ordering
-     * differs from the <code>&lt;</code> relation in that
-     * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
-     * NaN is considered greater than any other floating-point value.
-     * For the purposes of sorting, all NaN values are considered
-     * equivalent and equal.
-     * <p>
-     * 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 <tt>fromIndex &gt; toIndex</tt>
-     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
-     *         <tt>toIndex &gt; a.length</tt>
-     */
-    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
+        DualPivotQuicksort.sort(a, fromIndex, n - 1);
 
-        // Main sort phase: quicksort everything but the NaN's
-        sort1(a, fromIndex, n-fromIndex);
+        // Postprocessing phase: change 0.0d's to -0.0d's as required
+        if (numNegZeros != 0) {
+            int j = binarySearch0(a, fromIndex, n, 0.0d); // position of ANY zero
 
-        // Postprocessing phase: change 0.0's to -0.0's as required
-        if (numNegZeros != 0) {
-            int j = binarySearch0(a, fromIndex, n, 0.0d); // posn 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; k<numNegZeros; k++)
+            for (int k = 0; k < numNegZeros; k++) {
                 a[++j] = -0.0d;
+            }
         }
     }
 
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>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.
+     *
+     * <p>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
+     */
+    public static void sort(float[] a) {
+        sort(a, 0, a.length);
+    }
 
-    private static void sort2(float a[], int fromIndex, int toIndex) {
+    /**
+     * 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.
+     *
+     * <p>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.
+     *
+     * <p>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
+        DualPivotQuicksort.sort(a, fromIndex, n - 1);
 
-        // Main sort phase: quicksort everything but the NaN's
-        sort1(a, fromIndex, n-fromIndex);
+        // Postprocessing phase: change 0.0f's to -0.0f's as required
+        if (numNegZeros != 0) {
+            int j = binarySearch0(a, fromIndex, n, 0.0f); // position of ANY zero
 
-        // Postprocessing phase: change 0.0's to -0.0's as required
-        if (numNegZeros != 0) {
-            int j = binarySearch0(a, fromIndex, n, 0.0f); // posn 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; k<numNegZeros; k++)
+            for (int k = 0; k < numNegZeros; k++) {
                 a[++j] = -0.0f;
+            }
         }
     }
 
-
-    /*
-     * The code for each of the seven primitive types is largely identical.
-     * C'est la vie.
-     */
-
-    /**
-     * Sorts the specified sub-array of longs into ascending order.
-     */
-    private static void sort1(long x[], int off, int len) {
-        // Insertion sort on smallest arrays
-        if (len < 7) {
-            for (int i=off; i<len+off; i++)
-                for (int j=i; j>off && 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)* 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<n; i++, a++, b++)
-            swap(x, a, b);
-    }
-
-    /**
-     * Returns the index of the median of the three indexed longs.
-     */
-    private static int med3(long x[], int a, int b, int c) {
-        return (x[a] < x[b] ?
-                (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
-                (x[b] > 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; i<len+off; i++)
-                for (int j=i; j>off && 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)* 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<n; i++, a++, b++)
-            swap(x, a, b);
-    }
-
-    /**
-     * Returns the index of the median of the three indexed integers.
-     */
-    private static int med3(int x[], int a, int b, int c) {
-        return (x[a] < x[b] ?
-                (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
-                (x[b] > 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; i<len+off; i++)
-                for (int j=i; j>off && 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)* 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<n; i++, a++, b++)
-            swap(x, a, b);
-    }
-
-    /**
-     * Returns the index of the median of the three indexed shorts.
-     */
-    private static int med3(short x[], int a, int b, int c) {
-        return (x[a] < x[b] ?
-                (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
-                (x[b] > 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; i<len+off; i++)
-                for (int j=i; j>off && 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)* 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<n; i++, a++, b++)
-            swap(x, a, b);
-    }
-
-    /**
-     * Returns the index of the median of the three indexed chars.
-     */
-    private static int med3(char x[], int a, int b, int c) {
-        return (x[a] < x[b] ?
-                (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
-                (x[b] > 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; i<len+off; i++)
-                for (int j=i; j>off && 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)* 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<n; i++, a++, b++)
-            swap(x, a, b);
-    }
-
-    /**
-     * Returns the index of the median of the three indexed bytes.
-     */
-    private static int med3(byte x[], int a, int b, int c) {
-        return (x[a] < x[b] ?
-                (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
-                (x[b] > 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; i<len+off; i++)
-                for (int j=i; j>off && 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)* 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<n; i++, a++, b++)
-            swap(x, a, b);
-    }
-
-    /**
-     * Returns the index of the median of the three indexed doubles.
-     */
-    private static int med3(double x[], int a, int b, int c) {
-        return (x[a] < x[b] ?
-                (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
-                (x[b] > 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; i<len+off; i++)
-                for (int j=i; j>off && 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)* 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<n; i++, a++, b++)
-            swap(x, a, b);
-    }
-
-    /**
-     * Returns the index of the median of the three indexed floats.
-     */
-    private static int med3(float x[], int a, int b, int c) {
-        return (x[a] < x[b] ?
-                (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
-                (x[b] > 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, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
+     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
      *         <i>insertion point</i> 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 <tt>a.length</tt> 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 &gt;= 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, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
+     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
      *         <i>insertion point</i> 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 <tt>toIndex</tt> 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 &gt;= 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 <tt>true</tt> if the two specified arrays of Objects are
      * <i>equal</i> 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 "[]";
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/util/DualPivotQuicksort.java	Thu Oct 29 19:55:52 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);
+    }
+}
--- a/src/share/classes/sun/security/krb5/EncryptionKey.java	Thu Oct 29 09:22:00 2009 -0700
+++ b/src/share/classes/sun/security/krb5/EncryptionKey.java	Thu Oct 29 19:55:52 2009 -0700
@@ -1,5 +1,5 @@
 /*
- * Portions Copyright 2000-2007 Sun Microsystems, Inc.  All Rights Reserved.
+ * Portions Copyright 2000-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
@@ -503,7 +503,19 @@
                              + '\n'));
     }
 
+    /**
+     * Find a key with given etype
+     */
     public static EncryptionKey findKey(int etype, EncryptionKey[] keys)
+            throws KrbException {
+        return findKey(etype, null, keys);
+    }
+
+    /**
+     * Find a key with given etype and kvno
+     * @param kvno if null, return any (first?) key
+     */
+    public static EncryptionKey findKey(int etype, Integer kvno, EncryptionKey[] keys)
         throws KrbException {
 
         // check if encryption type is supported
@@ -516,7 +528,8 @@
         for (int i = 0; i < keys.length; i++) {
             ktype = keys[i].getEType();
             if (EType.isSupported(ktype)) {
-                if (etype == ktype) {
+                Integer kv = keys[i].getKeyVersionNumber();
+                if (etype == ktype && (kvno == null || kvno.equals(kv))) {
                     return keys[i];
                 }
             }
@@ -528,8 +541,11 @@
             for (int i = 0; i < keys.length; i++) {
                 ktype = keys[i].getEType();
                 if (ktype == EncryptedData.ETYPE_DES_CBC_CRC ||
-                    ktype == EncryptedData.ETYPE_DES_CBC_MD5) {
-                    return new EncryptionKey(etype, keys[i].getBytes());
+                        ktype == EncryptedData.ETYPE_DES_CBC_MD5) {
+                    Integer kv = keys[i].getKeyVersionNumber();
+                    if (kvno == null || kvno.equals(kv)) {
+                        return new EncryptionKey(etype, keys[i].getBytes());
+                    }
                 }
             }
         }
--- a/src/share/classes/sun/security/krb5/KrbApReq.java	Thu Oct 29 09:22:00 2009 -0700
+++ b/src/share/classes/sun/security/krb5/KrbApReq.java	Thu Oct 29 19:55:52 2009 -0700
@@ -268,7 +268,8 @@
     private void authenticate(EncryptionKey[] keys, InetAddress initiator)
         throws KrbException, IOException {
         int encPartKeyType = apReqMessg.ticket.encPart.getEType();
-        EncryptionKey dkey = EncryptionKey.findKey(encPartKeyType, keys);
+        Integer kvno = apReqMessg.ticket.encPart.getKeyVersionNumber();
+        EncryptionKey dkey = EncryptionKey.findKey(encPartKeyType, kvno, keys);
 
         if (dkey == null) {
             throw new KrbException(Krb5.API_INVALID_ARG,
--- a/src/share/classes/sun/security/krb5/internal/ktab/KeyTab.java	Thu Oct 29 09:22:00 2009 -0700
+++ b/src/share/classes/sun/security/krb5/internal/ktab/KeyTab.java	Thu Oct 29 19:55:52 2009 -0700
@@ -395,6 +395,28 @@
         }
     }
 
+    /**
+     * Only used by KDC test. This method can specify kvno and does not
+     * remove any old keys.
+     */
+    public void addEntry(PrincipalName service, char[] psswd, int kvno)
+         throws KrbException {
+
+        EncryptionKey[] encKeys = EncryptionKey.acquireSecretKeys(
+            psswd, service.getSalt());
+
+        for (int i = 0; encKeys != null && i < encKeys.length; i++) {
+            int keyType = encKeys[i].getEType();
+            byte[] keyValue = encKeys[i].getBytes();
+            KeyTabEntry newEntry = new KeyTabEntry(service,
+                            service.getRealm(),
+                            new KerberosTime(System.currentTimeMillis()),
+                                               kvno, keyType, keyValue);
+            if (entries == null)
+                entries = new Vector<KeyTabEntry> ();
+            entries.addElement(newEntry);
+        }
+    }
 
     /**
      * Retrieves the key table entry with the specified service name.
--- a/src/share/classes/sun/security/tools/JarSigner.java	Thu Oct 29 09:22:00 2009 -0700
+++ b/src/share/classes/sun/security/tools/JarSigner.java	Thu Oct 29 19:55:52 2009 -0700
@@ -1483,6 +1483,7 @@
         Timestamp timestamp = signer.getTimestamp();
         if (timestamp != null) {
             s.append(printTimestamp(tab, timestamp));
+            s.append('\n');
         }
         // display the certificate(s)
         for (Certificate c : certs) {
--- a/src/share/classes/sun/security/tools/KeyTool.java	Thu Oct 29 09:22:00 2009 -0700
+++ b/src/share/classes/sun/security/tools/KeyTool.java	Thu Oct 29 19:55:52 2009 -0700
@@ -26,6 +26,7 @@
 package sun.security.tools;
 
 import java.io.*;
+import java.security.CodeSigner;
 import java.security.KeyStore;
 import java.security.KeyStoreException;
 import java.security.MessageDigest;
@@ -34,6 +35,7 @@
 import java.security.PrivateKey;
 import java.security.Security;
 import java.security.Signature;
+import java.security.Timestamp;
 import java.security.UnrecoverableEntryException;
 import java.security.UnrecoverableKeyException;
 import java.security.Principal;
@@ -46,6 +48,8 @@
 import java.text.Collator;
 import java.text.MessageFormat;
 import java.util.*;
+import java.util.jar.JarEntry;
+import java.util.jar.JarFile;
 import java.lang.reflect.Constructor;
 import java.net.URL;
 import java.net.URLClassLoader;
@@ -130,6 +134,7 @@
     private File ksfile = null;
     private InputStream ksStream = null; // keystore stream
     private String sslserver = null;
+    private String jarfile = null;
     private KeyStore keyStore = null;
     private boolean token = false;
     private boolean nullStream = false;
@@ -206,7 +211,7 @@
             "-providername", "-providerclass", "-providerarg",
             "-providerpath", "-v", "-protected"),
         PRINTCERT("Prints the content of a certificate",
-            "-rfc", "-file", "-sslserver", "-v"),
+            "-rfc", "-file", "-sslserver", "-jarfile", "-v"),
         PRINTCERTREQ("Prints the content of a certificate request",
             "-file", "-v"),
         SELFCERT("Generates a self-signed certificate",
@@ -266,6 +271,7 @@
         {"-srcstorepass", "<arg>", "source keystore password"},
         {"-srcstoretype", "<srcstoretype>", "source keystore type"},
         {"-sslserver", "<server[:port]>", "SSL server host and port"},
+        {"-jarfile", "<filename>", "signed jar file"},
         {"-startdate", "<startdate>", "certificate validity start date/time"},
         {"-storepass", "<arg>", "keystore password"},
         {"-storetype", "<storetype>", "keystore type"},
@@ -453,6 +459,8 @@
                 outfilename = args[++i];
             } else if (collator.compare(flags, "-sslserver") == 0) {
                 sslserver = args[++i];
+            } else if (collator.compare(flags, "-jarfile") == 0) {
+                jarfile = args[++i];
             } else if (collator.compare(flags, "-srckeystore") == 0) {
                 srcksfname = args[++i];
             } else if ((collator.compare(flags, "-provider") == 0) ||
@@ -2065,7 +2073,71 @@
     }
 
     private void doPrintCert(final PrintStream out) throws Exception {
-        if (sslserver != null) {
+        if (jarfile != null) {
+            JarFile jf = new JarFile(jarfile, true);
+            Enumeration<JarEntry> entries = jf.entries();
+            Set<CodeSigner> ss = new HashSet<CodeSigner>();
+            byte[] buffer = new byte[8192];
+            int pos = 0;
+            while (entries.hasMoreElements()) {
+                JarEntry je = entries.nextElement();
+                InputStream is = null;
+                try {
+                    is = jf.getInputStream(je);
+                    while (is.read(buffer) != -1) {
+                        // we just read. this will throw a SecurityException
+                        // if a signature/digest check fails. This also
+                        // populate the signers
+                    }
+                } finally {
+                    if (is != null) {
+                        is.close();
+                    }
+                }
+                CodeSigner[] signers = je.getCodeSigners();
+                if (signers != null) {
+                    for (CodeSigner signer: signers) {
+                        if (!ss.contains(signer)) {
+                            ss.add(signer);
+                            out.printf(rb.getString("Signer #%d:"), ++pos);
+                            out.println();
+                            out.println();
+                            out.println(rb.getString("Signature:"));
+                            out.println();
+                            for (Certificate cert: signer.getSignerCertPath().getCertificates()) {
+                                X509Certificate x = (X509Certificate)cert;
+                                if (rfc) {
+                                    out.println(rb.getString("Certificate owner: ") + x.getSubjectDN() + "\n");
+                                    dumpCert(x, out);
+                                } else {
+                                    printX509Cert(x, out);
+                                }
+                                out.println();
+                            }
+                            Timestamp ts = signer.getTimestamp();
+                            if (ts != null) {
+                                out.println(rb.getString("Timestamp:"));
+                                out.println();
+                                for (Certificate cert: ts.getSignerCertPath().getCertificates()) {
+                                    X509Certificate x = (X509Certificate)cert;
+                                    if (rfc) {
+                                        out.println(rb.getString("Certificate owner: ") + x.getSubjectDN() + "\n");
+                                        dumpCert(x, out);
+                                    } else {
+                                        printX509Cert(x, out);
+                                    }
+                                    out.println();
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+            jf.close();
+            if (ss.size() == 0) {
+                out.println(rb.getString("Not a signed jar file"));
+            }
+        } else if (sslserver != null) {
             SSLContext sc = SSLContext.getInstance("SSL");
             final boolean[] certPrinted = new boolean[1];
             sc.init(null, new TrustManager[] {
--- a/src/share/classes/sun/security/util/Resources.java	Thu Oct 29 09:22:00 2009 -0700
+++ b/src/share/classes/sun/security/util/Resources.java	Thu Oct 29 19:55:52 2009 -0700
@@ -162,6 +162,8 @@
                 "source keystore type"}, //-srcstoretype
         {"SSL server host and port",
                 "SSL server host and port"}, //-sslserver
+        {"signed jar file",
+                "signed jar file"}, //=jarfile
         {"certificate validity start date/time",
                 "certificate validity start date/time"}, //-startdate
         {"keystore password",
@@ -370,6 +372,13 @@
 
         {"*****************  WARNING WARNING WARNING  *****************",
             "*****************  WARNING WARNING WARNING  *****************"},
+        {"Signer #%d:", "Signer #%d:"},
+        {"Timestamp:", "Timestamp:"},
+        {"Signature:", "Signature:"},
+        {"Certificate owner: ", "Certificate owner: "},
+        {"Not a signed jar file", "Not a signed jar file"},
+        {"No certificate from the SSL server",
+                "No certificate from the SSL server"},
 
         // Translators of the following 5 pairs, ATTENTION:
         // the next 5 string pairs are meant to be combined into 2 paragraphs,
--- a/test/sun/security/krb5/auto/KDC.java	Thu Oct 29 09:22:00 2009 -0700
+++ b/test/sun/security/krb5/auto/KDC.java	Thu Oct 29 19:55:52 2009 -0700
@@ -466,7 +466,17 @@
             // the krb5.conf config file would be loaded.
             Method stringToKey = EncryptionKey.class.getDeclaredMethod("stringToKey", char[].class, String.class, byte[].class, Integer.TYPE);
             stringToKey.setAccessible(true);
-            return new EncryptionKey((byte[]) stringToKey.invoke(null, getPassword(p), getSalt(p), null, etype), etype, null);
+            Integer kvno = null;
+            // For service whose password ending with a number, use it as kvno
+            if (p.toString().indexOf('/') >= 0) {
+                char[] pass = getPassword(p);
+                if (Character.isDigit(pass[pass.length-1])) {
+                    kvno = pass[pass.length-1] - '0';
+                }
+            }
+            return new EncryptionKey((byte[]) stringToKey.invoke(
+                    null, getPassword(p), getSalt(p), null, etype),
+                    etype, kvno);
         } catch (InvocationTargetException ex) {
             KrbException ke = (KrbException)ex.getCause();
             throw ke;
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/sun/security/krb5/auto/MoreKvno.java	Thu Oct 29 19:55:52 2009 -0700
@@ -0,0 +1,70 @@
+/*
+ * 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.
+ *
+ * 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.
+ */
+
+/*
+ * @test
+ * @bug 6893158
+ * @summary AP_REQ check should use key version number
+ */
+
+import sun.security.jgss.GSSUtil;
+import sun.security.krb5.PrincipalName;
+import sun.security.krb5.internal.ktab.KeyTab;
+
+public class MoreKvno {
+
+    public static void main(String[] args)
+            throws Exception {
+
+        OneKDC kdc = new OneKDC(null);
+        kdc.writeJAASConf();
+
+        // Rewrite keytab, 3 set of keys with different kvno
+        KeyTab ktab = KeyTab.create(OneKDC.KTAB);
+        PrincipalName p = new PrincipalName(OneKDC.SERVER+"@"+OneKDC.REALM, PrincipalName.KRB_NT_SRV_HST);
+        ktab.addEntry(p, "pass0".toCharArray(), 0);
+        ktab.addEntry(p, "pass2".toCharArray(), 2);
+        ktab.addEntry(p, "pass1".toCharArray(), 1);
+        ktab.save();
+
+        kdc.addPrincipal(OneKDC.SERVER, "pass1".toCharArray());
+        go(OneKDC.SERVER, "com.sun.security.jgss.krb5.accept");
+        kdc.addPrincipal(OneKDC.SERVER, "pass2".toCharArray());
+        // "server" initiate also, check pass2 is used at authentication
+        go(OneKDC.SERVER, "server");
+    }
+
+    static void go(String server, String entry) throws Exception {
+        Context c, s;
+        c = Context.fromUserPass("dummy", "bogus".toCharArray(), false);
+        s = Context.fromJAAS(entry);
+
+        c.startAsClient(server, GSSUtil.GSS_KRB5_MECH_OID);
+        s.startAsServer(GSSUtil.GSS_KRB5_MECH_OID);
+
+        Context.handshake(c, s);
+
+        s.dispose();
+        c.dispose();
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/sun/security/tools/keytool/readjar.sh	Thu Oct 29 19:55:52 2009 -0700
@@ -0,0 +1,56 @@
+#
+# 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.
+#
+# 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.
+#
+
+# @test
+# @bug 6890872
+# @summary keytool -printcert to recognize signed jar files
+#
+
+if [ "${TESTJAVA}" = "" ] ; then
+  JAVAC_CMD=`which javac`
+  TESTJAVA=`dirname $JAVAC_CMD`/..
+fi
+
+# set platform-dependent variables
+OS=`uname -s`
+case "$OS" in
+  Windows_* )
+    FS="\\"
+    ;;
+  * )
+    FS="/"
+    ;;
+esac
+
+KS=readjar.jks
+rm $KS
+$TESTJAVA${FS}bin${FS}keytool -storepass changeit -keypass changeit -keystore $KS \
+        -alias x -dname CN=X -genkeypair
+$TESTJAVA${FS}bin${FS}jar cvf readjar.jar $KS
+$TESTJAVA${FS}bin${FS}jarsigner -storepass changeit -keystore $KS readjar.jar x
+
+$TESTJAVA${FS}bin${FS}keytool -printcert -jarfile readjar.jar || exit 1
+$TESTJAVA${FS}bin${FS}keytool -printcert -jarfile readjar.jar -rfc || exit 1
+
+exit 0
+