How to determine if a List is sorted in Java?
Solution 1
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 null
s 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);
Solution 2
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.
Solution 3
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;
}
Solution 4
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.
Solution 5
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.
Related videos on Youtube
Eric Wilson
Software developer, experienced in Java and Python in Linux environments, formerly a professor of mathematics. I'm a father of five children, and a husband of one wife.
Updated on December 29, 2021Comments
-
Eric Wilson over 2 years
I would like a method that takes a
List<T>
whereT
implementsComparable
and returnstrue
orfalse
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.
-
Juliet almost 14 yearsAny chance you can use a sorted collection instead? Or just call .Sort() as needed instead?
-
Eric Wilson almost 14 yearsThe purpose of this is for testing, so no.
-
João Portela almost 14 yearsis the list supposed to be in ascending or descending order?
-
Eric Wilson almost 14 yearsI'd like to be able to check both, as both types will occur.
-
Admin almost 14 yearsgenerics have nothing to do with sorting or comparability, they have to do with Type safety and that is all.
-
Eric Wilson almost 14 years@fuzzy lollipop -- I was hoping to implement this method in type-safe way.
-
-
Yishai almost 14 yearsCollections.sort would require that the list elements be comparable already, and that was a stipulation in the question in any event.
-
BalusC almost 14 yearsThis keeps continuing because
previous
will never be set. See answer of Daniel for right flow. -
Eric Wilson almost 14 yearsI think your first example is missing a line, since
tmp
is not populated. -
ColinD almost 14 yearsWould need to be constrained to
<T extends Comparable>
as well of course. -
mikera almost 14 yearsp.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.
-
jjnguy almost 14 years@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.
-
ColinD almost 14 yearsThe first example is also pretty wasteful for what it does, and the Objects in the second need to be Comparable.
-
mikera almost 14 yearsInterestingly, your algorithm is actually O(1) expected time for reasonably random lists.
-
ColinD almost 14 yearsOne thing that could be done in this case would be to check if the
List
implementsRandomAccess
and use this implementation if so and anIterator
implementation if not. You wouldn't really want to use this with aLinkedList
as is. -
Jesper almost 14 yearsIt would be O(n) in the worst case (when the list is indeed sorted).
-
mikera almost 14 years@ColinD great idea! I'm guessing you could do this so that it detects this at compile as well
-
Kevin Bourrillion almost 14 yearsAnd there is also
isStrictlyOrdered()
if you want to make sure there are no duplicates. -
Kevin Bourrillion almost 14 years-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.
-
Eric Wilson almost 14 yearsI've accepted the solution that avoids using raw types. This was my second choice, though, so I've upvoted it.
-
jjnguy almost 14 years@FarmBoy, Thanks for the feed back! Glad we could help.
-
JUST MY correct OPINION almost 14 years+1 for pointing to existing code so that people stop reinventing things and start making new things.
-
Rana Ghosh over 9 yearsCan you show an example of this if there is no natural ordering and you want to pass in a
Comparator
? I think that's whatOrdering.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." -
ColinD over 9 years@tieTYT: You can using
Ordering.from(comparator).isOrdered(list)
; if you're implementing the comparator yourself, though, you might as well just extendOrdering
rather than implementingComparator
to begin with, in which case it's justmyOrdering.isOrdered(list)
. -
Rann Lifshitz almost 8 yearsFollowing the suggestion to use Ordering.from(comparator).isOrdered(list): Using a Java 8 lambda expression in order to implement the comparator parameter of the from method can be a useful and elegant solution for customized ordering.
-
Ben Page over 7 yearsfwiw, 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.
-
Eric Wilson over 7 yearsNice ... obviously didn't help 2010 me using Java 6, but this is a good addition.
-
ShellFish over 7 yearsThis is so much better than sorting the array and checking if they are equal.
-
Vadzim almost 7 yearsMuch less effective than ideal allocation-less and sorting-less solution.
-
johnlemon almost 7 yearsAccording 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
-
Palle almost 7 yearsIt 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.
-
Moses Kirathe about 6 years@Daniel Does prev need to be initialized?
-
Andrea Bergonzo almost 5 yearsJust leaving a note here. Most of ordering is Obsolete but they removed the comments for planned deletion here. github.com/google/guava/commit/…
-
Mingjiang Shi over 4 yearsIt 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.
-
Daniel over 2 years@MosesKirathe: Yes