title: Collections.sort() Fails In large ArrayList, Frequently sorted
body: <p>I've seen a lot of posts related to this issue but every desk check I've performed and suggestion I've implemented did not help. I can't figure out how I am violating the contract of the comparator. Granted I don't use comparators that often.</p>
  
  <p>I have a large ArrayList of objects that are sorted on every update because their positions frequently change. I have to render these objects form bottom-left to top-right order to preserve a 'depth' like look to a 2D program.</p>
  
  <p>Here is my comparator:</p>
  
  <pre><code>@Override
  public int compare(RenderObject o1, RenderObject o2) 
  {
      //if(o1 == null || o2 == null)
      //    return 0;
  
      if(o1 == null)
          return -1;
      else if(o2 == null)
          return 1;
  
      //vertices in order top-left, top-right, bottom-right, bottom-left
      PointF[]    bounds1 = o1.getVertices(),
                  bounds2 = o2.getVertices();
  
      //if(bounds1 == null || bounds2 == null || bounds1.equals(bounds2))
      //  return 0;
  
      if(bounds1 == null)
          return -1;
      else if(bounds2 == null)
          return 1;
  
      if(bounds1[0].x &gt;= bounds2[1].x || bounds1[3].y &lt;= bounds2[0].y)
          return 1;
      else if(bounds1[1].x &lt;= bounds2[0].x || bounds1[0].y &gt;= bounds2[3].y)
          return -1;
  
      return o1.getZOrder() &lt; o2.getZOrder() ? 1 : (o1.getZOrder() &gt; o2.getZOrder() ? -1 : 0);
  }
  </code></pre>
  
  <p>Can someone please explain where the contract is violated. I tried desk checking with the same exact vertices for both o1 &amp; o2 and couldn't figure out how they are not equal. If it can't be helped I suppose I'll have to implement sorting manually, it would probably be more efficient since not all objects will move every update, but I would still like to fix this code, if for nothing else future reference.</p>
  
  <p>EDIT: Here is the actual error, but it's right where all other's stop with this issue.</p>
  
  <pre><code>Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
  at java.util.TimSort.mergeLo(Unknown Source)
  at java.util.TimSort.mergeAt(Unknown Source)
  at java.util.TimSort.mergeForceCollapse(Unknown Source)
  at java.util.TimSort.sort(Unknown Source)
  at java.util.TimSort.sort(Unknown Source)
  at java.util.Arrays.sort(Unknown Source)
  at java.util.Collections.sort(Unknown Source)
  at ....Map.update(Map.java:237)
  at ....GameMain.update(GameMain.java:76)
  at ....BasicGame.start(BasicGame.java:173)
  at ....GameMain.main(GameMain.java:121)
  </code></pre>