Неправильный порядок обнаружения при сортировке параллельного потока

У меня есть класс Record:

public class Record implements Comparable<Record>
{
   private String myCategory1;
   private int    myCategory2;
   private String myCategory3;
   private String myCategory4;
   private int    myValue1;
   private double myValue2;

   public Record(String category1, int category2, String category3, String category4,
      int value1, double value2)
   {
      myCategory1 = category1;
      myCategory2 = category2;
      myCategory3 = category3;
      myCategory4 = category4;
      myValue1 = value1;
      myValue2 = value2;
   }

   // Getters here
}

Я создаю большой список из множества записей. Только второе и пятое значения, i / 10000 и i, используются позже геттерами getCategory2() и getValue1() соответственно.

List<Record> list = new ArrayList<>();
for (int i = 0; i < 115000; i++)
{
    list.add(new Record("A", i / 10000, "B", "C", i, (double) i / 100 + 1));
}

Обратите внимание, что первые 10 000 записей имеют category2 из 0, затем следующие 10 000 имеют 1 и т. д., а значения value1 последовательно равны 0–114999.

Я создаю Stream, который одновременно является parallel и sorted.

Stream<Record> stream = list.stream()
   .parallel()
   .sorted(
       //(r1, r2) -> Integer.compare(r1.getCategory2(), r2.getCategory2())
   )
   //.parallel()
;

У меня есть ForkJoinPool, который поддерживает 8 потоков, то есть количество ядер на моем ПК.

ForkJoinPool pool = new ForkJoinPool(8);

Я использую прием, описанный здесь, чтобы отправить задачу обработки потока своему собственному ForkJoinPool вместо обычного ForkJoinPool.

List<Record> output = pool.submit(() ->
    stream.collect(Collectors.toList()
)).get();

Я ожидал, что параллельная операция sorted будет учитывать порядок встречи потока и что это будет стабильная сортировка, потому что Spliterator, возвращаемое ArrayList, равно ORDERED.

Однако простой код, выводящий элементы результирующего числа List output по порядку, показывает, что это не совсем так.

for (Record record : output)
{
     System.out.println(record.getValue1());
}

Выход, сжатый:

0
1
2
3
...
69996
69997
69998
69999
71875  // discontinuity!
71876
71877
71878
...
79058
79059
79060
79061
70000  // discontinuity!
70001
70002
70003
...
71871
71872
71873
71874
79062  // discontinuity!
79063
79064
79065
79066
...
114996
114997
114998
114999

size() из output это 115000, и все элементы кажутся там, просто в немного другом порядке.

Поэтому я написал код проверки, чтобы убедиться, что sort работает стабильно. Если он стабилен, то все значения value1 должны оставаться в порядке. Этот код проверяет заказ, распечатывая любые несоответствия.

int prev = -1;
boolean verified = true;
for (Record record : output)
{
    int curr = record.getValue1();
    if (prev != -1)
    {
        if (prev + 1 != curr)
        {
            System.out.println("Warning: " + prev + " followed by " + curr + "!");
            verified = false;
        }
    }
    prev = curr;
}
System.out.println("Verified: " + verified);

Выход:

Warning: 69999 followed by 71875!
Warning: 79061 followed by 70000!
Warning: 71874 followed by 79062!
Warning: 99999 followed by 100625!
Warning: 107811 followed by 100000!
Warning: 100624 followed by 107812!
Verified: false

Это состояние сохраняется, если я выполню одно из следующих действий:

• Замените ForkJoinPool на ThreadPoolExecutor.

  ThreadPoolExecutor pool = new ThreadPoolExecutor(8, 8, 0, TimeUnit.SECONDS, new ArrayBlockingQueue<>(10));
  

• Используйте общий ForkJoinPool, обрабатывая Stream напрямую.

  List<Record> output = stream.collect(Collectors.toList());
  

• Позвонить parallel() после того, как я позвоню sorted.

  Stream<Record> stream = list.stream().sorted().parallel();
  

• Позвоните parallelStream() вместо stream().parallel().

  Stream<Record> stream = list.parallelStream().sorted();
  

• Сортировка по Comparator. Обратите внимание, что этот критерий сортировки отличается от «естественного» порядка, который я определил для интерфейса Comparable, хотя, начиная с результатов, уже упорядоченных с самого начала, результат должен быть тем же самым.

  Stream<Record> stream = list.stream().parallel().sorted(
      (r1, r2) -> Integer.compare(r1.getCategory2(), r2.getCategory2())
  );
  

Я могу получить это, чтобы сохранить порядок столкновений, только если я не сделаю одно из следующих действий на Stream:

• Не звони parallel().
• Не вызывайте перегрузку sorted.

Интересно, что parallel() без сортировки сохранили порядок.

В обоих вышеперечисленных случаях вывод:

Verified: true

Моя версия Java 1.8.0_05. Эта аномалия также происходит на Ideone, который, по-видимому, работает под управлением Java 8u25.

Обновить

Я обновил свой JDK до последней версии на момент написания этой статьи, 1.8.0_45, и проблема не изменилась.

Вопрос

Является ли порядок записей в результирующем List (output) неправильным, потому что сортировка почему-то нестабильна, потому что порядок встреч не сохраняется, или по какой-то другой причине?

Как обеспечить сохранение порядка встреч при создании параллельного потока и его сортировке?