Sort algorithm changes in Java 7

I just got the info from one of out customers that an error in the export function of a Grails application happend. The stacktrace looked like:

Error Details

Error 500: Executing action [export] of controller [ExportController] caused exception: Runtime error executing action
Servlet: grails
URI: /app/grails/export/export.dispatch
Exception Message: Comparison method violates its general contract!
Caused by: Comparison method violates its general contract!
Class: ExportPrintController
At Line: [105]
Code Snippet:
Stack Trace

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(TimSort.java:868)
at java.util.TimSort.mergeAt(TimSort.java:485)
at java.util.TimSort.mergeCollapse(TimSort.java:408)
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)
at com.troii.app.web.ExportController$_closure2.doCall(ExportController.groovy:105)
at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1110)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:603)
at java.lang.Thread.run(Thread.java:722)

I did some web search and came up with this interesting discussion on stackoverflow. Which links to the compatibility information page of JDK7 and a specific change they made in Java 7: changing the default sort algorithm from MergeSort to TimSort in the java.util.Arrays.sort method.

So a quick workaround for this issue was to add -Djava.util.Arrays.useLegacyMergeSort=true to the tomcat JVM environment – which forces the app to use the old algorithm.

To really fix the issue I had to make a change to the code because it really violated the Comparable contract. Our code looked like:

int compare(ExportTerm e1, ExportTerm e2) {
  if (e1.sortLabel == null) {
    return -1
  }
  if (e2.sortLabel == null) {
    return 1
  }
  return collator.compare(e1.sortLabel, e2.sortLabel)
}

which is wrong, because if you compare two elements where the sortLabel is null on both, the return value would be -1 or 1, depending on the order you compare them – which violates the contract.

Correct it has to look like:

int compare(ExportTerm e1, ExportTerm e2) {
  if (e1.sortLabel == e2.sortLabel) {
    return 0
  }
  if (e1.sortLabel == null) {
    return -1
  }
  if (e2.sortLabel == null) {
    return 1
  }
  return collator.compare(e1.sortLabel, e2.sortLabel)
}

3 thoughts on “Sort algorithm changes in Java 7

  1. AnandBalaji

    public int compare(ExportTerm o1, ExportTerm o2) {

    if (o1 == o2)
    return 0;
    if (o1 == null)
    return -1;
    if (o2 == null)
    return 1;

    // Before sending the result as such after compare just check once’s whether the compare result returns 0.

    int result = option.compare(o1, o2);

    // So we will send the result only when != 0 so that order in the list is maintained in the same order as such

    if (result != 0) {
    return result;
    }

    // if nothing is returned from the method this is returned by default
    return 0;
    }

    Reply
  2. Oscar

    I don’t see why this (“if you compare two elements where the sortLabel is null on both, the return value would be -1 or 1, depending on the order you compare them”) violates the contract. Could you explain it a bit more, please? Thanks in advance

    Reply
    1. tompson Post author

      If both e1.sortLabel and e2.sortLabel are null the compare method should return 0 because they are equal. In the case of my first implementation it would return -1 which is wrong.

      Reply

Leave a Reply