title: "Comparison method violates its general contract!" - finding small sample data set
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/8327514/comparison-method-violates-its-general-contract">“Comparison method violates its general contract!”</a>  </p>
  </blockquote>
  
  
  
  <p>I have a larger sample of partially sorted data (> 700 items) which I want to sort with Java 7 and get the following exception:</p>
  
  <pre><code>java.lang.IllegalArgumentException: Comparison method violates its general contract!
      at java.util.TimSort.mergeLo(TimSort.java:747)
      at java.util.TimSort.mergeAt(TimSort.java:483)
      at java.util.TimSort.mergeCollapse(TimSort.java:410)
      at java.util.TimSort.sort(TimSort.java:214)
      at java.util.TimSort.sort(TimSort.java:173)
      at java.util.Arrays.sort(Arrays.java:659)
      at java.util.Collections.sort(Collections.java:217)
  </code></pre>
  
  <p>Now I'm trying to lower the size of the data set to make finding the reason simpler. I've written a small application which picks a random subset out of the larger set to reproduce the exception.</p>
  
  <pre><code>private static final int SUBSET_SIZE = 32;
  
  public void testSorting() {
      ...
      final Random random = new Random();
      for (int i = 10000000; i-- &gt; 0; ) {
          testFew(strings, random);
      }
  }
  
  private void testFew(List&lt;String&gt; strings, Random random) {
      final List&lt;String&gt; list = new ArrayList&lt;String&gt;();
      int index = 0;
      for (int i = 0; i &lt; SUBSET_SIZE; i++) {
          final int rnd = random.nextInt(strings.size() / 100) + 1;
          index = (index + rnd) % strings.size();
          list.add(strings.get(index));
      }
  
      try {
          Collections.sort(list, MY_COMPARATOR);
      }
      catch (RuntimeException ex) {
          for (String s : list) {
              System.err.println(s);
          }
          throw ex;
      }
  }
  </code></pre>
  
  <p>The strange thing is that finding a sample to reproduce is very simple if the subset contains <strong>at least 32 items</strong>, but I've did not succeeded in finding a smaller set. IMHO, this smells rather like a bug in the sorting algorithm than in our comparator.</p>