How to determine if a List is sorted in Java?

I would like a method that takes a List<T> where T implements Comparable and returns true or false depending on whether the list is sorted or not.

What is the best way to implement this in Java? It's obvious that generics and wildcards are meant to be able to handle such things easily, but I'm getting all tangled up.

It would also be nice to have an analogous method to check if the list is in reverse order.

Guava provides this functionality through its Comparators class.

boolean sorted = Comparators.isInOrder(list, comparator);

There's also the Ordering class, though this is mostly obsolete. An Ordering is a Comparator++. In this case, if you have a list of some type that implements Comparable, you could write:

boolean sorted = Ordering.natural().isOrdered(list);

This works for any Iterable, not just List, and you can handle nulls easily by specifying whether they should come before or after any other non-null elements:

Ordering.natural().nullsLast().isOrdered(list);

Also, since you mentioned that you'd like to be able to check for reverse order as well as normal, that would be done as:

Ordering.natural().reverse().isOrdered(list);

Stream

If you are using Java 8 or later, streams may be able to help.

list.stream().sorted().collect(Collectors.toList()).equals(list);

More briefly, in Java 16+, using Stream#toList.

list.stream().sorted().toList().equals(list);

This code will sort the list out of place and collect its elements in another list, which is then compared to the initial list. The comparison will be successful, if both lists contain the same elements in equal positions.

Note that this method will have worse space and time complexity than other approaches because it will have to sort the list out of place, so it should not be used for very large lists. But it is the easiest to use because it is a single expression and does not involve 3rd party libraries.

Here's a generic method that will do the trick:

public static <T extends Comparable<? super T>>
        boolean isSorted(Iterable<T> iterable) {
    Iterator<T> iter = iterable.iterator();
    if (!iter.hasNext()) {
        return true;
    }
    T t = iter.next();
    while (iter.hasNext()) {
        T t2 = iter.next();
        if (t.compareTo(t2) > 0) {
            return false;
        }
        t = t2;
    }
    return true;
}

Easy:

List tmp = new ArrayList(myList);
Collections.sort(tmp);
boolean sorted = tmp.equals(myList);

Or (if elements are comparable):

Object prev = null;
for( Object elem : myList ) {
    if( prev != null && prev.compareTo(elem) > 0 ) {
        return false;
    }
    prev = elem;
}
return true;

Or (if elements are not comparable):

Object prev = null;
for( Object elem : myList ) {
    if( prev != null && myComparator.compare(prev,elem) > 0 ) {
        return false;
    }
    prev = elem;
}
return true;

The implementations fail for lists containing null values. You have to add appropriate checks in this case.

If you need it for unit testing, you can use AssertJ. It contains an assertion to check if a List is sorted:

List<String> someStrings = ...
assertThat(someStrings).isSorted();

There is also an alternative method isSortedAccordingTo that takes a comparator in case you want to use a custom comparator for the sorting.

How to determine if a List is sorted in Java?

Stream

Related

Recent Posts