Subsorting with multiple Comparators

Question

I've seen a number of questions on Stack Overflow of the kind of "How do I sort on fields X AND Y?" The most common answers to those questions consists of "Write a custom Comparator."

But what if you have 3 fields you can sort on? Or 13? or 300? My solution is this utility class, so that rather than writing a billion different Comparators for every possible combination you might want, you write just 3 (or 13, etc.) simple ones and essentially composite them to get the desired behavior.

This method is designed to be used as essentially an expanded version of Collections.sort(List list, Comparator c) so I want to adhere to the same contract as much as possible.

I am also interested in ways to improve the documentation/API and finding possibly troublesome corner cases.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * A utility class for sorting a list using multiple sorting criteria.
 *
 */
public class Multisorter {
    /**
     * Sorts the given List using the given Comparators.
     * 
     * The List is sorted by the Comparators in the order the Comparators are
     * given; the elements are sorted according to the first Comparator, then
     * all of the elements that are considered "equal" are subsorted recursively
     * by the next Comparator and so on.
     * 
     * This method makes use of Collections.sort(List<T>, Comparator<T>)
     * internally and obeys the same contract.
     * 
     * @param <T>
     *            the generic type of the list.
     * 
     * @param list
     *            the List to sort
     * @param comparators
     *            the comparators to sort with
     * @return the sorted List
     */
    public static <T> void sort(List<T> list, Comparator<? super T>... comparators) {
        if (comparators.length <= 0) {
            throw new IllegalArgumentException("Must provide at least one Comparator to sort with.");
        }
        Collections.sort(list, comparators[0]);
        if (comparators.length > 1) {
            List<List<T>> subCollections = new ArrayList<>();
            for (T element : list) {
                boolean matchFound = false;
                for (List<T> subList : subCollections) {
                    if (comparators[0].compare(element, subList.get(0)) == 0) {
                        subList.add(element);
                        matchFound = true;
                    }
                    if (matchFound) {
                        break;
                    }
                }
                if (!matchFound) {
                    int lastIndex = subCollections.size();
                    subCollections.add(lastIndex, new ArrayList<>());
                    subCollections.get(lastIndex).add(element);
                }
            }

            // Sort each of the subcollections recursively without the first Comparator
            for (List<T> subList : subCollections) {
                sort(subList, Arrays.copyOfRange(comparators, 1, comparators.length));
            }
            // Aggregate all the subcollections
            list.clear();
            for (List<T> subList : subCollections) {
                list.addAll(subList);
            }
        }
    }
}

However, based on comments by Alnitak and rolfl, I would just use the new thenComparing method in Comparator added in Java 8 that I didn't know about.

Answer 1

I find your code fairly complicated. Especially the part where you split the list into sequences of sublists of equal elements is a bit convoluted. Here's what you're doing in pseudocode:

given a comparator,
for each element in the list:
    for each sublist:
       if per the comparator, the element is equal to an element in that sublist:
           add the element to the sublist,
           continue with next element
    if no sublist matched:
        add a new sublist containing that element

The most straightforward way to implement that in Java is using a labeled loop. Using that, we can continue with the next element in the outer loop once a match was found. We do not have to maintain a matchFound variable:

List<List<T>> subCollections = new ArrayList<>();

element:
for (T element : list) {
    for (List<T> subList : subCollections) {
        if (comparators[0].compare(element, subList.get(0)) == 0) {
            subList.add(element);
            continue element;
        }
    }
    // no sublist matched
    List<T> newList = new ArrayList<>();
    newList.add(element);
    subCollections.add(newList);
}

There's also no need to use a lastIndex here.

Unfortunately, what you are doing is tremendously inefficient. You re-sort each list multiple times, and invoke each comparator unnecessarily often. You are more or less implementing a crazy inefficient multi-level quicksort that partitions into multiple parts per level.

The better solution would be to create a custom comparator that loops through the list of comparators and stops when they are no longer equal:

class MultiComparator<T> implements Comparator<T> {
    private final List<Comparator<T>> comparators;

    public MultiComparator(List<Comparator<? super T>> comparators) {
        this.comparators = comparators;
    }

    public MultiComparator(Comparator<? super T>... comparators) {
        this(Arrays.asList(comparators));
    }

    public int compare(T o1, T o2) {
        for (Comparator<T> c : comparators) {
            int result = c.compare(o1, o2);
            if (result != 0) {
                return result;
            }
        }
        return 0;
    }

    public static <T> void sort(List<T> list, Comparator<? super T>... comparators) {
        Collections.sort(list, new MultiComparator<T>(comparators));
    }
}

(untested)

Answer 2

• Instead of checking for (comperators.length > 1) you can check for == 1 and use it as a guard condition. In this way you are saving horizontal space.

  if (comparators.length == 1) {
      return ;
  }  
  

• you have boilerplate code in your inner loop. You first set matchFound = true and then breakif matchFound == true.

  for (List<T> subList : subCollections) {
      if (comparators[0].compare(element, subList.get(0)) == 0) {
          subList.add(element);
          break;
      }
  }  
  

• you are iterating over subCollections but name the items subList this seems strange IMHO.

• instead of clearing the list at the end and then adding the items of the subCollections you should consider to change the return type from void to List<T>.