public class StableSortBug {
    static final int SIZE = 50_000;

    static class Record implements Comparable<Record> {
        final int sortVal;
        final int seqNum;

        Record(int i1, int i2) { sortVal = i1; seqNum = i2; }

        @Override
        public int compareTo(Record other) {
            return Integer.compare(this.sortVal, other.sortVal);
        }
    }

    static Record[] genArray() {
        Record[] array = new Record[SIZE];
        Arrays.setAll(array, i -> new Record(i / 10_000, i));
        return array;
    }

    static boolean verify(Record[] array) {
        return IntStream.range(1, array.length)
                        .allMatch(i -> array[i-1].seqNum + 1 == array[i].seqNum);
    }

    public static void main(String[] args) {
        Record[] array = genArray();
        System.out.println(verify(array));
        Arrays.sort(array);
        System.out.println(verify(array));
        Arrays.parallelSort(array);
        System.out.println(verify(array));
    }
}

This should print

    true
    true
    true

every time, but with the right values it will print

    true
    true
    false

indicating that the parallel sort has disturbed the order. On my machine (2 cores x 2 threads, 3GHz MBP 2014) it fails every time. Reducing the size to 20,000 will restore stability. Changing the divisor to 1,000 (reducing the number of consecutive values that compare equal) will also restore stability.

Credit to Stack Overflow user rgettman for finding this.

http://stackoverflow.com/questions/30406281/encounter-order-wrong-when-sorting-a-parallel-stream