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


ADDITIONAL OS VERSION INFORMATION :
Linux 3.13.0-48-generic #80-Ubuntu SMP Thu Mar 12 11:16:15 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux


EXTRA RELEVANT SYSTEM CONFIGURATION :
Runtime.availableProcessors = 12

A DESCRIPTION OF THE PROBLEM :
java.util.Arrays.parallelSort is documented to be stable but is not: parallelSort can change the relative position of equal elements .

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the attached test case that sorts an array and checks if the sort was stable.

If the problem isn't immediately reproducible, try a machine with more processors, or try adjusting the array length or random seed.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The test case should complete without output.
ACTUAL -
Exception in thread "main" java.lang.AssertionError: sort wasn't stable: Record [key=31, originalIndex=583397] before Record [key=31, originalIndex=793]
at ParallelSortIsNotStable.main(ParallelSortIsNotStable.java:34)


REPRODUCIBILITY :
This bug can be reproduced often.

---------- BEGIN SOURCE ----------
import java.util.Arrays;
import java.util.Random;

public class ParallelSortIsNotStable {
private static class Record {
final int key;
final int originalIndex;

public Record(int key, int originalIndex) {
this.key = key;
this.originalIndex = originalIndex;
}

@Override
public String toString() {
return String.format("Record [key=%s, originalIndex=%s]", key, originalIndex);
}
}

public static void main(String[] args) {
Random rnd = new Random(0);

Record[] records = new Record[1000000];
for (int i = 0; i < records.length; ++i) {
records[i] = new Record(rnd.nextInt(1000), i);
}

Arrays.parallelSort(records, (r1, r2) -> Integer.compare(r1.key, r2.key));

for (int i = 1; i < records.length; ++i) {
Record prev = records[i - 1];
Record cur = records[i];
if (prev.key == cur.key && prev.originalIndex > cur.originalIndex) {
throw new AssertionError("sort wasn't stable: " + prev + " before " + cur);
}
}
}
}

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

CUSTOMER SUBMITTED WORKAROUND :
Use Arrays.sort, which is stable, instead.