85

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.

6
  • Any chance you can use a sorted collection instead? Or just call .Sort() as needed instead?
    – Juliet
    Jun 15, 2010 at 16:29
  • 1
    The purpose of this is for testing, so no. Jun 15, 2010 at 16:54
  • is the list supposed to be in ascending or descending order? Jun 15, 2010 at 17:11
  • I'd like to be able to check both, as both types will occur. Jun 15, 2010 at 18:21
  • 1
    @fuzzy lollipop -- I was hoping to implement this method in type-safe way. Jun 15, 2010 at 19:30

14 Answers 14

136

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);
6
  • 11
    And there is also isStrictlyOrdered() if you want to make sure there are no duplicates. Jun 15, 2010 at 19:10
  • 12
    +1 for pointing to existing code so that people stop reinventing things and start making new things. Jun 16, 2010 at 1:10
  • Can you show an example of this if there is no natural ordering and you want to pass in a Comparator? I think that's what Ordering.from is for: "Returns an ordering based on an existing comparator instance. Note that it is unnecessary to create a new anonymous inner class implementing Comparator just to pass it in here. Instead, simply subclass Ordering and implement its compare method directly." Sep 4, 2014 at 19:22
  • 3
    @tieTYT: You can using Ordering.from(comparator).isOrdered(list); if you're implementing the comparator yourself, though, you might as well just extend Ordering rather than implementing Comparator to begin with, in which case it's just myOrdering.isOrdered(list).
    – ColinD
    Sep 4, 2014 at 19:24
  • 1
    Just leaving a note here. Most of ordering is Obsolete but they removed the comments for planned deletion here. github.com/google/guava/commit/… Jun 7, 2019 at 14:58
42

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.

4
  • 1
    Nice ... obviously didn't help 2010 me using Java 6, but this is a good addition. Oct 25, 2016 at 12:29
  • 8
    Much less effective than ideal allocation-less and sorting-less solution.
    – Vadzim
    May 27, 2017 at 23:26
  • According to Java 8 docs, Collectors.toList(); There are no guarantees on the type, mutability, serializability, or thread-safety of the {@code List} returned; You should use a supplier of ArrayList
    – johnlemon
    Jun 8, 2017 at 8:32
  • 5
    It does not look like this is relevant for this case, as the generated list never outlives is statement, so it will never be serialized, mutated or accessed from multiple threads.
    – Palle
    Jun 8, 2017 at 22:05
29

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;
}
23

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.

5
  • Collections.sort would require that the list elements be comparable already, and that was a stipulation in the question in any event.
    – Yishai
    Jun 15, 2010 at 16:32
  • 3
    I think your first example is missing a line, since tmp is not populated. Jun 15, 2010 at 16:44
  • 1
    The first example is also pretty wasteful for what it does, and the Objects in the second need to be Comparable.
    – ColinD
    Jun 15, 2010 at 16:49
  • @Daniel Does prev need to be initialized? Mar 14, 2018 at 5:02
  • @MosesKirathe: Yes
    – Daniel
    Dec 22, 2021 at 10:07
10

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.

5

To check whether a list or any data structure for that matter is a task that only takes O(n) time. Just iterate over the list using the Iterator Interface and run through the data (in your case you already have it ready as a type of Comparable) from start to end and you can find whether its sorted or not easily

3
  • 1
    Interestingly, your algorithm is actually O(1) expected time for reasonably random lists.
    – mikera
    Jun 15, 2010 at 16:51
  • 1
    It would be O(n) in the worst case (when the list is indeed sorted).
    – Jesper
    Jun 15, 2010 at 17:13
  • 5
    -1 since the asker has indicated he's getting "tangled up" in implementation issues like generics and wildcards, I think this answer is only telling him things he already knows. Jun 15, 2010 at 19:13
5
private static <T extends Comparable<? super T>> boolean isSorted(List<T> array){
    for (int i = 0; i < array.size()-1; i++) {
        if(array.get(i).compareTo(array.get(i+1))> 0){
            return false;
        }
    }
    return true;
}

zzzzz not sure guys what you guys are doing but this can be done in simple for loop.

2
  • 1
    fwiw, the implementation of the library in the accepted answer (Guava) is essentially this: github.com/google/guava/blob/… But IMO it's always better to keep your codebase small rather than reimplementing things a library can give you.
    – Ben Page
    Sep 23, 2016 at 13:30
  • This is so much better than sorting the array and checking if they are equal.
    – ShellFish
    Nov 28, 2016 at 15:46
4

Simply use the iterator to look through the contents of the List<T>.

public static <T extends Comparable> boolean isSorted(List<T> listOfT) {
    T previous = null;
    for (T t: listOfT) {
        if (previous != null && t.compareTo(previous) < 0) return false;
        previous = t;
    }
    return true;
}
5
  • 3
    This keeps continuing because previous will never be set. See answer of Daniel for right flow.
    – BalusC
    Jun 15, 2010 at 16:32
  • Would need to be constrained to <T extends Comparable> as well of course.
    – ColinD
    Jun 15, 2010 at 16:45
  • @Colin (and everyone else) I am sorry that this doesn't compile. I wrote it very quickly. Colin, you have edit power, feel free to fix this error I made.
    – jjnguy
    Jun 15, 2010 at 16:49
  • I've accepted the solution that avoids using raw types. This was my second choice, though, so I've upvoted it. Jun 15, 2010 at 19:36
  • @FarmBoy, Thanks for the feed back! Glad we could help.
    – jjnguy
    Jun 15, 2010 at 19:41
2

Using Java 8 streams:

boolean isSorted = IntStream.range(1, list.size())
        .map(index -> list.get(index - 1).compareTo(list.get(index)))
        .allMatch(order -> order <= 0);

This also works for empty lists. It is however only efficient for lists that also implement the RandomAccess marker interface (e.g., ArrayList).

If you do not have access to the stream's underlying collection, the following ugly hack can be used:

Stream<T> stream = ...
Comparator<? super T> comparator = ...
boolean isSorted = new AtomicInteger(0) {{
    stream.sequential()
          .reduce((left, right) -> {
               getAndUpdate(order -> (order <= 0) ? comparator.compare(left, right) : order);
               return right;
          });
}}.get() <= 0;
1

This is an operation that will take O(n) time (worst case). You will need to handle two cases: where the list is sorted in descending order, and where the list is sorted in ascending order.

You will need to compare each element with the next element while making sure that the order is preserved.

1

This is what I would do:

public static <T extends Comparable<? super T>> boolean isSorted(List<T> list) {
    if (list.size() != 0) {
        ListIterator<T> it = list.listIterator();
        for (T item = it.next(); it.hasNext(); item = it.next()) {
            if (it.hasPrevious() && it.previous().compareTo(it.next()) > 0) {
                return false;
            }
        }

    }
    return true;
}
1
  • It doesn't work. ``` public static void main(String[] args) { List<Integer> list = Arrays.asList(1,2,9,7,4); System.out.println(isSorted(list)); } ``` expecte print false, but print true. Aug 20, 2019 at 8:26
0

One simple implementation on arrays:

public static <T extends Comparable<? super T>> boolean isSorted(T[] a, int start, int end) {
    while (start<end) {
        if (a[start].compareTo(a[start+1])>0) return false;
        start++;
    }
    return true;
}

Converting for lists:

public static <T extends Comparable<? super T>> boolean isSorted(List<T> a) {
    int length=a.size();
    if (length<=1) return true;

    int i=1;
    T previous=a.get(0);
    while (i<length) {
        T current=a.get(i++);
        if (previous.compareTo(current)>0) return false;
        previous=current;
    }
    return true;
}
3
  • 1
    p.s. note the implementation is deliberately designed to avoid allocating an iterator or making multiple calls to get. This is designed for the common case where you are using an ArrayList, for other list implementation you are probably better off using the iterator.
    – mikera
    Jun 15, 2010 at 16:48
  • One thing that could be done in this case would be to check if the List implements RandomAccess and use this implementation if so and an Iterator implementation if not. You wouldn't really want to use this with a LinkedList as is.
    – ColinD
    Jun 15, 2010 at 16:59
  • @ColinD great idea! I'm guessing you could do this so that it detects this at compile as well
    – mikera
    Jun 15, 2010 at 17:20
0

Here comes a method using an Iterable and a Comparator.

<T> boolean isSorted(Iterable<? extends T> iterable,
                     Comparator<? super T> comparator) {
    boolean beforeFirst = true;
    T previous = null;
    for (final T current : iterable) {
        if (beforeFirst) {
            beforeFirst = false;
            previous = current;
            continue;
        }
        if (comparator.compare(previous, current) > 0) {
            return false;
        }
        previous = current;
    }
    return true;
}

And a method for an Iterable of Comparable and a flag for ordering.

<T extends Comparable<? super T>> boolean isSorted(
        Iterable<? extends T> iterable, boolean natural) {
    return isSorted(iterable, natural ? naturalOrder() : reverseOrder());
}
0

IMO, from what I'm seeing, the complexity of checking this is as bad as performing the sort for a second time, and I understand people are short circuiting with returns if it is not sorted, but if the List is actually sorted, then the entire length will be traversed..., I'd argue to just let the code continue as if the List was sorted, and let the code itself figure out if it is or not.

I would recommend placing an Error detailing why the specific line that will fail is doing so because its collection is not reversed/ordered etc...

eg.

the line detachTailIndex.run() will give a NullPointerException(),

if (fromReversedMethod && detachTailIndex == null) {
throw new NullPointerException("detachTailIndex was null. \n 
Reason: The List<> is required to be reversed before submission")
}

Or if your plan is to use a conditional for when sorted or not the you can use the null to verify if it is sorted and choose the other option.

If there is no other option, then using the other responses are ok.

Here is another example:

    int key = entry.getKey();
    
    List<Integer> shouldBeReversed = entry.getValue();

    try {
        //If all entries need to be iterated better place them inside the Try-Catch
            updateBatch(key,
                    xes -> {
                        for (int rowIndex : shouldBeReversed
                        ) {
                            xes.remove((int) rowIndex); // will return an IndexOutOfBoundsException if not sorted in reverse
                        }
                        return xes;
                    }
            );
    } catch (IndexOutOfBoundsException e) {
        throw new IndexOutOfBoundsException(e.getMessage() + "\n" +
                "Reason: Batch indexes (Entry's value \"List<Integer>\") should be sorted in reverse order before submission");
    }

if conditional is required (on sorted, or on not sorted) then the catch() body could be used as a "not sorted" option.

Of course this is very very case specific, but seems that checking for a sorting order just to get a boolean seems too much (?) specially on iterations.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.