diff -r 4ebc2e2fb97c -r 71c04702a3d5 test/jdk/java/util/Arrays/SortingNearlySortedPrimitive.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/jdk/java/util/Arrays/SortingNearlySortedPrimitive.java	Tue Sep 12 19:03:39 2017 +0200
@@ -0,0 +1,354 @@
+/*
+ * Copyright 2015 Goldman Sachs.
+ * Copyright (c) 2015, 2016, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+/*
+ * @test
+ * @bug 8154049
+ * @summary Tests the sorting of a large array of sorted primitive values,
+ *          predominently for cases where the array is nearly sorted. This tests
+ *          code that detects patterns in the array to determine if it is nearly
+ *          sorted and if so employs and optimizes merge sort rather than a
+ *          Dual-Pivot QuickSort.
+ *
+ * @run testng SortingNearlySortedPrimitive
+ */
+
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.StringJoiner;
+import java.util.function.IntFunction;
+import java.util.stream.IntStream;
+import java.util.stream.Stream;
+
+public class SortingNearlySortedPrimitive {
+
+    static final int BASE = 3;
+    static final int WIDTH = 4;
+    // Should be > DualPivotQuicksort.QUICKSORT_THRESHOLD
+    static final int PAD = 300;
+
+    Stream<int[]> createCombinations() {
+        // Create all combinations for the BASE value and double the WIDTH
+        // elements
+        // This is create various combinations of ascending, descending and
+        // equal runs to exercise the nearly sorted code paths
+        return IntStream.range(0, (int) Math.pow(BASE, 2 * WIDTH)).
+                mapToObj(this::createArray);
+    }
+
+    // Create an array which at either end is filled with -ve and +ve elements
+    // according to the base value and padded with zeros in between
+    int[] createArray(int v) {
+        int[] a = new int[WIDTH + PAD + WIDTH];
+
+        // Fill head of array
+        for (int j = 0; j < WIDTH; j++) {
+            a[j] = (v % BASE) - (BASE / 2);
+            v /= BASE;
+        }
+        // Fill tail of array
+        for (int j = 0; j < WIDTH; j++) {
+            a[WIDTH + PAD + j] = (v % BASE) - (BASE / 2);
+            v /= BASE;
+        }
+        return a;
+    }
+
+    @Test
+    public void testCombination() {
+        createCombinations().forEach(a -> {
+            try {
+                // Clone source array to ensure it is not modified
+                this.sortAndAssert(a.clone());
+                this.sortAndAssert(floatCopyFromInt(a));
+                this.sortAndAssert(doubleCopyFromInt(a));
+                this.sortAndAssert(longCopyFromInt(a));
+                this.sortAndAssert(shortCopyFromInt(a));
+                this.sortAndAssert(charCopyFromInt(a));
+            } catch (AssertionError sae) {
+                AssertionError ae = new AssertionError("Sort failed for " + arrayToString(a));
+                ae.addSuppressed(sae);
+                throw ae;
+            }
+        });
+    }
+
+    String arrayToString(int[] a) {
+        int[] l = Arrays.copyOfRange(a, 0, WIDTH + 2);
+        int[] r = Arrays.copyOfRange(a, a.length - (WIDTH + 2), a.length);
+        StringJoiner sj = new StringJoiner(",", "[", "]");
+        for (int i : l) {
+            sj.add(Integer.toString(i));
+        }
+        sj.add("...");
+        for (int i : r) {
+            sj.add(Integer.toString(i));
+        }
+        return sj.toString();
+    }
+
+
+    @DataProvider(name = "shapes")
+    public Object[][] createShapes() {
+        Stream<List<Object>> baseCases = Stream.of(
+                List.of("hiZeroLowTest", (IntFunction<int[]>) this::hiZeroLowData),
+                List.of("endLessThanTest", (IntFunction<int[]>) this::endLessThanData),
+                List.of("highFlatLowTest", (IntFunction<int[]>) this::highFlatLowData),
+                List.of("identicalTest", (IntFunction<int[]>) this::identicalData),
+                List.of("sortedReversedSortedTest", (IntFunction<int[]>) this::sortedReversedSortedData),
+                List.of("pairFlipTest", (IntFunction<int[]>) this::pairFlipData),
+                List.of("zeroHiTest", (IntFunction<int[]>) this::zeroHiData)
+        );
+
+        // Ensure the following inequality holds for certain sizes
+        // DualPivotQuicksort.QUICKSORT_THRESHOLD <= size - 1
+        //   < DualPivotQuicksort.COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR
+        // This guarantees that code paths are taken for checking nearly sorted
+        // arrays for all primitive types
+        List<Integer> sizes = List.of(100, 1_000, 10_000, 1_000_000);
+        return baseCases.
+                flatMap(l -> sizes.stream().map(s -> append(l, s))).
+                toArray(Object[][]::new);
+    }
+
+    Object[] append(List<Object> l, Object value) {
+        List<Object> nl = new ArrayList<>(l);
+        nl.add(value);
+        return nl.toArray();
+    }
+
+    @Test(dataProvider = "shapes")
+    public void testShapes(String testName, IntFunction<int[]> dataMethod, int size) {
+        int[] intSourceArray = dataMethod.apply(size);
+
+        // Clone source array to ensure it is not modified
+        this.sortAndAssert(intSourceArray.clone());
+        this.sortAndAssert(floatCopyFromInt(intSourceArray));
+        this.sortAndAssert(doubleCopyFromInt(intSourceArray));
+        this.sortAndAssert(longCopyFromInt(intSourceArray));
+        this.sortAndAssert(shortCopyFromInt(intSourceArray));
+        this.sortAndAssert(charCopyFromInt(intSourceArray));
+    }
+
+    private float[] floatCopyFromInt(int[] src) {
+        float[] result = new float[src.length];
+        for (int i = 0; i < result.length; i++) {
+            result[i] = src[i];
+        }
+        return result;
+    }
+
+    private double[] doubleCopyFromInt(int[] src) {
+        double[] result = new double[src.length];
+        for (int i = 0; i < result.length; i++) {
+            result[i] = src[i];
+        }
+        return result;
+    }
+
+    private long[] longCopyFromInt(int[] src) {
+        long[] result = new long[src.length];
+        for (int i = 0; i < result.length; i++) {
+            result[i] = src[i];
+        }
+        return result;
+    }
+
+    private short[] shortCopyFromInt(int[] src) {
+        short[] result = new short[src.length];
+        for (int i = 0; i < result.length; i++) {
+            result[i] = (short) src[i];
+        }
+        return result;
+    }
+
+    private char[] charCopyFromInt(int[] src) {
+        char[] result = new char[src.length];
+        for (int i = 0; i < result.length; i++) {
+            result[i] = (char) src[i];
+        }
+        return result;
+    }
+
+    private void sortAndAssert(int[] array) {
+        Arrays.sort(array);
+        for (int i = 1; i < array.length; i++) {
+            if (array[i] < array[i - 1]) {
+                throw new AssertionError("not sorted");
+            }
+        }
+    }
+
+    private void sortAndAssert(char[] array) {
+        Arrays.sort(array);
+        for (int i = 1; i < array.length; i++) {
+            if (array[i] < array[i - 1]) {
+                throw new AssertionError("not sorted");
+            }
+        }
+    }
+
+    private void sortAndAssert(short[] array) {
+        Arrays.sort(array);
+        for (int i = 1; i < array.length; i++) {
+            if (array[i] < array[i - 1]) {
+                throw new AssertionError("not sorted");
+            }
+        }
+    }
+
+    private void sortAndAssert(double[] array) {
+        Arrays.sort(array);
+        for (int i = 1; i < array.length; i++) {
+            if (array[i] < array[i - 1]) {
+                throw new AssertionError("not sorted");
+            }
+        }
+    }
+
+    private void sortAndAssert(float[] array) {
+        Arrays.sort(array);
+        for (int i = 1; i < array.length; i++) {
+            if (array[i] < array[i - 1]) {
+                throw new AssertionError("not sorted");
+            }
+        }
+    }
+
+    private void sortAndAssert(long[] array) {
+        Arrays.sort(array);
+        for (int i = 1; i < array.length; i++) {
+            if (array[i] < array[i - 1]) {
+                throw new AssertionError("not sorted");
+            }
+        }
+    }
+
+    private int[] zeroHiData(int size) {
+        int[] array = new int[size];
+
+        int threeQuarters = (int) (size * 0.75);
+        for (int i = 0; i < threeQuarters; i++) {
+            array[i] = 0;
+        }
+        int k = 1;
+        for (int i = threeQuarters; i < size; i++) {
+            array[i] = k;
+            k++;
+        }
+
+        return array;
+    }
+
+    private int[] hiZeroLowData(int size) {
+        int[] array = new int[size];
+
+        int oneThird = size / 3;
+        for (int i = 0; i < oneThird; i++) {
+            array[i] = i;
+        }
+        int twoThirds = oneThird * 2;
+        for (int i = oneThird; i < twoThirds; i++) {
+            array[i] = 0;
+        }
+        for (int i = twoThirds; i < size; i++) {
+            array[i] = oneThird - i + twoThirds;
+        }
+        return array;
+    }
+
+    private int[] highFlatLowData(int size) {
+        int[] array = new int[size];
+
+        int oneThird = size / 3;
+        for (int i = 0; i < oneThird; i++) {
+            array[i] = i;
+        }
+        int twoThirds = oneThird * 2;
+        int constant = oneThird - 1;
+        for (int i = oneThird; i < twoThirds; i++) {
+            array[i] = constant;
+        }
+        for (int i = twoThirds; i < size; i++) {
+            array[i] = constant - i + twoThirds;
+        }
+
+        return array;
+    }
+
+    private int[] identicalData(int size) {
+        int[] array = new int[size];
+        int listNumber = 24;
+
+        for (int i = 0; i < size; i++) {
+            array[i] = listNumber;
+        }
+
+        return array;
+    }
+
+    private int[] endLessThanData(int size) {
+        int[] array = new int[size];
+
+        for (int i = 0; i < size - 1; i++) {
+            array[i] = 3;
+        }
+        array[size - 1] = 1;
+
+        return array;
+    }
+
+    private int[] sortedReversedSortedData(int size) {
+        int[] array = new int[size];
+
+        for (int i = 0; i < size / 2; i++) {
+            array[i] = i;
+        }
+        int num = 0;
+        for (int i = size / 2; i < size; i++) {
+            array[i] = size - num;
+            num++;
+        }
+
+        return array;
+    }
+
+    private int[] pairFlipData(int size) {
+        int[] array = new int[size];
+
+        for (int i = 0; i < size; i++) {
+            array[i] = i;
+        }
+        for (int i = 0; i < size; i += 2) {
+            int temp = array[i];
+            array[i] = array[i + 1];
+            array[i + 1] = temp;
+        }
+
+        return array;
+    }
+}