Sorting list of files in android throwing 'Comparison method violates its general contract!'

Question

It's happening on my Android application & here is the stack trace:

Caused by java.lang.IllegalArgumentException: Comparison method violates its general contract!
       at java.util.TimSort.mergeHi(TimSort.java:864)
       at java.util.TimSort.mergeAt(TimSort.java:481)
       at java.util.TimSort.mergeForceCollapse(TimSort.java:422)
       at java.util.TimSort.sort(TimSort.java:219)
       at java.util.TimSort.sort(TimSort.java:169)
       at java.util.Arrays.sort(Arrays.java:2023)
       at java.util.Collections.sort(Collections.java:1883)

Here is my sort logic:

private static void sortFiles(List<File> listFiles, int sortDirection) {
    try {
      if (sortDirection == sortLatestFirst) {
        Collections.sort(listFiles, new LatestFirstComparator());
        ...

Here is the comparator:

class LatestFirstComparator implements Comparator<File> {
  @Override
  public int compare(File f1, File f2) {
    return Long.compare(f2.lastModified(), f1.lastModified());
  }
}

I've found related questions & other solutions, but none of them solves my problem. Moreover, this is not a consistent behavior, but happening only with some of the app users.

Answer 1

As said by others, the problem lies in the fact that the value of the last modified timestamp can change during the sort operation. In order to sort reliably, you have to cache the values for the duration of the sort operation:

private static void sortFiles(List<File> listFiles, int sortDirection) {
    if(listFiles.isEmpty()) return;
    Map<File,Long> cache = new HashMap<>();
    Comparator<File> byTime
        = Comparator.comparing(f -> cache.computeIfAbsent(f, File::lastModified));
    if(sortDirection == sortLatestFirst) byTime = byTime.reversed();
    listFiles.sort(byTime);
}

I assume that you use a notification mechanism for changes anyway, to decide when to reload the file list, so the sorting operation does not need to deal with it.

If you want to support an API level that doesn’t support Java 8 features, you have to use the more verbose variant

private static void sortFiles(List<File> listFiles, int sortDirection) {
    if(listFiles.isEmpty()) return;
    final Map<File,Long> cache = new HashMap<File,Long>();
    Comparator<File> byTime = new Comparator<File>() {
        @Override
        public int compare(File f1, File f2) {
            Long t1 = cache.get(f1), t2 = cache.get(f2);
            if(t1 == null) cache.put(f1, t1 = f1.lastModified());
            if(t2 == null) cache.put(f2, t2 = f2.lastModified());
            return t1.compareTo(t2);
        }
    };
    if(sortDirection == sortLatestFirst) byTime = Collections.reverseOrder(byTime);
    Collections.sort(listFiles, byTime);
}