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

Also reproduced on:
jdk1.7.0_05
jdk1.7.0_25
jdk1.7.0_40
jdk1.7.0_45
jdk1.7.0_51
jdk1.7.0_75
jdk1.8.0_25
jdk1.8.0_40
jdk1.8.0_45
jdk1.8.0_65

ADDITIONAL OS VERSION INFORMATION :
Linux themisto.intranet.aselta.com 2.6.32-642.15.1.el6.x86_64 #1 SMP Fri Feb 24 14:31:22 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

A DESCRIPTION OF THE PROBLEM :
I'm trying to sort an array of Point2D.Double, using a comparator in y coordinate, then x coordinate with tolerance. The data only contains numeric values (no NaN, no infinity).

On a particular data set, Arrays.sort() throws "Comparison method violates its general contract!".

I have brute-force tested that my comparator respects the Comparator.compare() contracts on thousands of other data sets. The data set reproducing the bug is too large (1.4 million elements) to exhaustively test the comparator on it. I have tried testing various ranges or random selections of this data set without reproducing the bug.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
The data is too large to directly paste it here, so I created a project that reproduces the issue (prerequisites: git, maven)

1) Download project
git clone https://github.com/nicoulaj/sort-bug.git

2) Launch tests
mvn test


EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
No test failure.
ACTUAL -
The test case SortBugTest.testSortByYthenX() fails with a "Comparison method violates its general contract!" exception.

ERROR MESSAGES/STACK TRACES THAT OCCUR :
java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(TimSort.java:899)
at java.util.TimSort.mergeAt(TimSort.java:516)
at java.util.TimSort.mergeForceCollapse(TimSort.java:457)
at java.util.TimSort.sort(TimSort.java:254)
at java.util.Arrays.sort(Arrays.java:1438)
at net.nicoulaj.SortBugTest.testSortByYthenX(SortBugTest.java:96)

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
The source code available in the test project (see "Steps to Reproduce").

Direct link to test code: https://github.com/nicoulaj/sort-bug/blob/master/src/test/java/net/nicoulaj/SortBugTest.java

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