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 :
Both Arrays.parallelSort() and Stream.parallel().sorted() get stuck when all the fork/join threads in the common pool are currently blocked. This can happen when they are doing IO, blocking on locks or are running long operations.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Easy to reproduce.

We start by grabbing a thread from the common fork join pool (we'll use that later).

Park all threads in common pool, in addition to the thread that submitted the task (see "nasty" thread).

We then generate random numbers in parallel (this works).

We submit 4 jobs to the pool to be executed concurrently. We are able to sort sequentially, but not in parallel. Only when we unpark the thread we grabbed earlier from the common FJPool thread. Now the parallel sorting returns again.


EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
It should've sorted in parallel using just the submitting thread.
ACTUAL -
someFJThread = Thread[ForkJoinPool.commonPool-worker-1,5,main]
sortingParallelWithStreams start
sortingSequentialWithStreams start
sortingParallelWithArrays start
sortingSequentialWithArrays start
Waiting for the threads to finish
-2147396095
sortingSequentialWithArrays done
IntSummaryStatistics{count=10000000, sum=-7907867979643, min=-2147483050, average=-790786.797964, max=2147482405}
sortingSequentialWithStreams done
Waiting for the threads to finish
Waiting for the threads to finish
Waiting for the threads to finish
Waiting for the threads to finish
Waiting for the threads to finish
Waiting for the threads to finish
Waiting for the threads to finish
Waiting for the threads to finish
Waiting for the threads to finish
Unparking one FJ thread
 ... Waiting for the threads to finish
IntSummaryStatistics{count=10000000, sum=-7907867979643, min=-2147483050, average=-790786.797964, max=2147482405}
sortingParallelWithStreams done
-2147396095
sortingParallelWithArrays done
All done!


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
import java.util.stream.*;

/**
 * Both Arrays.parallelSort() and Stream.parallel().sorted()
 * get stuck when all the fork/join threads in the common pool
 * are currently blocked.
 * <p>
 * We start by grabbing a thread from the common fork join pool
 * (we'll use that later).
 * <p>
 * Park all threads in common pool, in addition to the thread
 * that submitted the task (see "nasty" thread).
 * <p>
 * We then generate random numbers in parallel (this works).
 * <p>
 * We submit 4 jobs to the pool to be executed concurrently. We
 * are able to sort sequentially, but not in parallel. Only when
 * we unpark the thread we grabbed earlier from the common FJPool
 * thread. Now the parallel sorting returns again.
 */
public class ParallelSortBug2 {
  public static void main(String... args) throws Exception {
    Thread someFJThread = ForkJoinPool.commonPool().submit(
        Thread::currentThread).get();

    System.out.println("someFJThread = " + someFJThread);

    new Thread("nasty") {
      { setDaemon(true);}

      public void run() {
        IntStream.range(0, Runtime.getRuntime().availableProcessors())
            .parallel().forEach(i1 -> LockSupport.park());
      }
    }.start();

    Thread.sleep(100);

    // we can still generate our random array in parallel
    int[] numbers = ThreadLocalRandom.current().ints(10_000_000)
        .parallel().toArray();

    ExecutorService pool = Executors.newCachedThreadPool();

    pool.submit(() -> {
      System.out.println("sortingParallelWithStreams start");
      System.out.println(IntStream.of(numbers.clone()).
          parallel().sorted().summaryStatistics());
      System.out.println("sortingParallelWithStreams done");
    });

    pool.submit(() -> {
      System.out.println("sortingSequentialWithStreams start");
      System.out.println(IntStream.of(numbers.clone()).
          sorted().summaryStatistics());
      System.out.println("sortingSequentialWithStreams done");
    });

    pool.submit(() -> {
      System.out.println("sortingParallelWithArrays start");
      int[] toSort = numbers.clone();
      Arrays.parallelSort(toSort);
      System.out.println(toSort[204]);
      System.out.println("sortingParallelWithArrays done");
    });

    pool.submit(() -> {
      System.out.println("sortingSequentialWithArrays start");
      int[] toSort = numbers.clone();
      Arrays.sort(toSort);
      System.out.println(toSort[204]);
      System.out.println("sortingSequentialWithArrays done");
    });


    pool.shutdown();

    for (int i = 0; i < 10 && !pool.awaitTermination(1, TimeUnit.SECONDS); i++) {
      System.out.println("Waiting for the threads to finish");
    }

    System.out.println("Unparking one FJ thread");
    LockSupport.unpark(someFJThread);

    while (!pool.awaitTermination(1, TimeUnit.SECONDS)) {
      System.out.println(" ... Waiting for the threads to finish");
    }

    System.out.println("All done!");
  }
}

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

CUSTOMER SUBMITTED WORKAROUND :
Hard to work around this, except to not use parallel sorting. For Arrays.parallelSort(), the user has to do something explicitly, but for stream.parallel().sorted(), it would be more common that this can happen without the user realizing why it does not return.

Of course, we should never call blocking operations inside our common fork/join threads :-)