FULL PRODUCT VERSION :
java version "1.8.0_92"
Java(TM) SE Runtime Environment (build 1.8.0_92-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.92-b14, mixed mode)


ADDITIONAL OS VERSION INFORMATION :
Darwin sparky.local 15.5.0 Darwin Kernel Version 15.5.0: Tue Apr 19 18:36:36 PDT 2016; root:xnu-3248.50.21~8/RELEASE_X86_64 x86_64

A DESCRIPTION OF THE PROBLEM :
Internally, Arrays.parallelSort() looks at the parallelism of the common fork/join pool to decide whether to sort an array in parallel. The default parallelism is equal to Runtime.getRuntime().availableProcessors() - 1. However, if you have a single-core machine, then the common parallelism is set to 1, not 0. Thus the parallelSort() method cannot differentiate between machines with 1 and 2 CPUs.



STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
In my example below, if you start the program with -Djava.util.concurrent.ForkJoinPool.common.parallelism=0 (as if you have a single CPU) or with -Djava.util.concurrent.ForkJoinPool.common.parallelism=1 (as if you have a dual-core machine) you will see that it only has a common parallelism of 1 and thus the array is sorted sequentially only.

If you change it to 2 (signifying 3 cores), then it works in parallel.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
I was expecting the dual-core machine (without hyperthreading) to sort in parallel.
ACTUAL -
java -Djava.util.concurrent.ForkJoinPool.common.parallelism=1 ParallelSortBug1
parallelism property = 1
pool.getCommonPoolParallelism() = 1
sequentialTime = 1068
parallelTime = 884
sequentialTime = 844
parallelTime = 804
sequentialTime = 855
parallelTime = 897
sequentialTime = 867
parallelTime = 899
sequentialTime = 825
parallelTime = 802
sequentialTime = 799
parallelTime = 793
sequentialTime = 881
parallelTime = 888
sequentialTime = 883
parallelTime = 899
sequentialTime = 862
parallelTime = 869
sequentialTime = 910
parallelTime = 903

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.io.*;
import java.util.*;
import java.util.concurrent.*;

/**
 * Arrays.parallelSort() does not sort in parallel for dual-core
 * machines.
 *
 * Internally, Arrays.parallelSort() looks at the parallelism
 * of the common fork/join pool to decide whether to sort an
 * array in parallel. The default parallelism is equal to
 * Runtime.getRuntime().availableProcessors() - 1. However, if
 * you have a single-core machine, then the common parallelism is
 * set to 1, not 0. Thus the parallelSort() method cannot
 * differentiate between machines with 1 and 2 CPUs.
 *
 * In this example, if you start the program with
 * -Djava.util.concurrent.ForkJoinPool.common.parallelism=0
 * or with
 * -Djava.util.concurrent.ForkJoinPool.common.parallelism=1
 * you will see that it only has a common parallelism of 1 and
 * thus the array is sorted sequentially only.
 *
 * If you change it to 2 (signifying 3 cores), then it works in
 * parallel.
 */
public class ParallelSortBug1 {
  public static void main(String... args) throws IOException {
    System.out.println("parallelism property = " +
        System.getProperty("java.util.concurrent.ForkJoinPool.common.parallelism"));
    ForkJoinPool pool = ForkJoinPool.commonPool();
    System.out.println("pool.getCommonPoolParallelism() = " +
        pool.getCommonPoolParallelism());

    // generate int[] of random numbers
    int[] numbers = ThreadLocalRandom.current().ints(10_000_000)
        .parallel().toArray();

    for (int i = 0; i < 10; i++) {
      long sequentialTime = System.currentTimeMillis();
      Arrays.sort(numbers.clone());
      sequentialTime = System.currentTimeMillis() - sequentialTime;
      System.out.println("sequentialTime = " + sequentialTime);

      long parallelTime = System.currentTimeMillis();
      Arrays.parallelSort(numbers.clone());
      parallelTime = System.currentTimeMillis() - parallelTime;

      System.out.println("parallelTime = " + parallelTime);
    }
  }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
On a dual-core machine, we would need to start with -Djava.util.concurrent.ForkJoinPool.common.parallelism=2, but this means that all the parallel streams would be using one additional thread to do the processing.