Subsorting with multiple Comparators

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, Comparator)
* internally and obeys the same contract.
*
* @param
* 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 void sort(List list, Comparator... comparators) {
if (comparators.length 1) {
List> subCollections = new ArrayList<>();
for (T element : list) {
boolean matchFound = false;

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> subCollections = new ArrayList<>();

element:
for (T element : list) {
    for (List subList : subCollections) {
        if (comparators[0].compare(element, subList.get(0)) == 0) {
            subList.add(element);
            continue element;
        }
    }
    // no sublist matched
    List 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 implements Comparator {
    private final List> comparators;

    public MultiComparator(List> comparators) {
        this.comparators = comparators;
    }

    public MultiComparator(Comparator... comparators) {
        this(Arrays.asList(comparators));
    }

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

    public static  void sort(List list, Comparator... comparators) {
        Collections.sort(list, new MultiComparator(comparators));
    }
}

(untested)

StackExchange Code Review Q#74758, answer score: 6