Checking If a List Is Sorted in Java

1. Overview

In this tutorial, we’ll see different ways to check if a list is sorted in Java.

2. Iterative Approach

The iterative approach is a simple and intuitive way to check for a sorted list. In this approach, we’ll iterate the list and compare the adjacent elements. If any of the two adjacent elements are not sorted, we can say that the list is not sorted.

A list can be either sorted in the natural order or in a custom order. We’ll cover both these cases using Comparable and Comparator interfaces.

2.1. Using Comparable

First, let’s see an example of a list whose elements are of type Comparable. Here, we’ll consider a list containing objects of type String:

public static boolean isSorted(List<String> listOfStrings) {
    if (isEmpty(listOfStrings) || listOfStrings.size() == 1) {
        return true;
    }

    Iterator<String> iter = listOfStrings.iterator();
    String current, previous = iter.next();
    while (iter.hasNext()) {
        current = iter.next();
        if (previous.compareTo(current) > 0) {
            return false;
        }
        previous = current;
    }
    return true;
}

2.2. Using Comparator

Now, let’s consider an Employee class, which does not implement Comparable. So, in this case, we need to use a Comparator to compare the adjacent elements of the list:

public static boolean isSorted(List<Employee> employees, Comparator<Employee> employeeComparator) {
    if (isEmpty(employees) || employees.size() == 1) {
        return true;
    }

    Iterator<Employee> iter = employees.iterator();
    Employee current, previous = iter.next();
    while (iter.hasNext()) {
        current = iter.next();
        if (employeeComparator.compare(previous, current) > 0) {
            return false;
        }
        previous = current;
    }
    return true;
}

The above two examples are similar. The only difference is in how we compare the previous and the current elements of the list.

In addition, we can also use Comparator to have precise control over the sorting check. Further information about these two is available in our Comparator and Comparable in Java tutorial.

3. Recursive Approach

Now, we’ll see how to check for a sorted list using recursion:

public static boolean isSorted(List<String> listOfStrings) {
    return isSorted(listOfStrings, listOfStrings.size());
}

public static boolean isSorted(List<String> listOfStrings, int index) {
    if (index < 2) {
        return true;
    } else if (listOfStrings.get(index - 2).compareTo(listOfStrings.get(index - 1)) > 0) {
        return false;
    } else {
        return isSorted(listOfStrings, index - 1);
    }
}

4. Using Guava

It’s often good to use a third-party library instead of writing our own logic. The Guava library has some utility classes that we can use to check if a list is sorted.

4.1. Guava Ordering Class

In this section, we’ll see how to use the Ordering class in Guava to check for a sorted list.

First, we’ll see an example of a list containing elements of type Comparable:

public static boolean isSorted(List<String> listOfStrings) {
    return Ordering.<String> natural().isOrdered(listOfStrings);
}

Next, we’ll see how we can check if a list of Employee objects is sorted using a Comparator:

public static boolean isSorted(List<Employee> employees, Comparator<Employee> employeeComparator) {
    return Ordering.from(employeeComparator).isOrdered(employees);
}

Also, we can use natural().reverseOrder() to check if a list is sorted in reverse order. In addition, we can use natural().nullFirst() and natural().nullLast() to check if null appears to the first or the last of the sorted list.

To know more about Guava Ordering class, we can refer our Guide to Guava’s Ordering article.

4.2. Guava Comparators Class

If we are using Java 8 or above, Guava provides a better alternative in terms of Comparators class. We’ll see an example of using the isInOrder method of this class:

public static boolean isSorted(List<String> listOfStrings) {
    return Comparators.isInOrder(listOfStrings, Comparator.<String> naturalOrder());
}

As we can see, in the above example, we’ve used the natural ordering to check for a sorted list. We can also use a Comparator to customize the sorting check.

5. Conclusion

In this article, we’ve seen how we can check for a sorted list using a simple iterative approach, a recursive approach, and using Guava. We’ve also briefly touched upon the usage of Comparator and Comparable in deciding the sorting check logic.