Is the list sorted?

Is the trade-off between simplicity and performance worth it?

def is_sorted(list_):
"""
Is the list sorted?

The simpler list_ == list(sorted(list_)) has
time complexity O(N log N), this O(n).

>>> is_sorted([1, 2, 3])
True
>>> is_sorted([1, 2, 7, 3])
False
"""
return all(curr <= list_[index + 1]
for index, curr in enumerate(list_[:-1]))

• I think you'd have to be dealing with a lot of large, mostly-already-sorted lists to beat the cost of calling the function and making a copy of the list (the slice, another O(n)). You can't determine if it's worth it a priori. Commented Jun 22, 2015 at 17:57
• @jonrsharpe interesting, so this function may be slower than the alternative despite the time-complexity... this is what I get when I don't benchmark. :) Commented Jun 22, 2015 at 17:58
• Well, maybe. O(2n) is still O(n), after all. But there are fixed costs to consider too. Commented Jun 22, 2015 at 18:01
• "pythonic way to check if a list is sorted or not": stackoverflow.com/questions/3755136/… Commented Jun 22, 2015 at 20:22

In my opinion the cleanest way to do this is with itertools.tee. It basically makes an arbitrary number of copies of iterators. This avoids having to make a copy of the list (which any slice-based approach would do), avoids having to do any math or indexing, and works on arbitrary iterables, not just lists.

try:
itertools.izip as zip
except ImportError:
pass
from itertools import tee

def issorted(mylist):
if not mylist:
return True
list1, list2 = tee(mylist)  # make two copies of the list's iterator
next(list2)  # advance one copy one element
return all(a<=b for a, b in zip(list1, list2))

• Instead of tee you could use the builtin iter in a similar way: list2 = iter(mylist); next(list2) Commented Jun 23, 2015 at 5:44
• Yes, if you are sure you will only ever have certain types. Assuming the data type isn't really idiomatic, though. Commented Jun 23, 2015 at 6:43

This can be written much more simply with izip from itertools. This removes having to fiddle with indices that enumerate gives back. Of course, it should probably also have a check for an list of length 0 or 1 as well.

return all(x <= y for x, y in izip(list, list[1:]))


Edit: The problem with built-in zip for Python 2 is that it will completely construct the list again in memory, which will kill performance for a large list. If you really want code that's portable between both Python 2 and 3, I'd suggest something like:

try:
from itertools import izip
except ImportError:
izip = zip

• No need for a special case, it already works for zero and one elements. Commented Jun 22, 2015 at 18:45
• By the way, I would avoid Python-2 only methods, in Python-3: >>> from itertools import izip Traceback (most recent call last): File "<pyshell#0>", line 1, in <module> from itertools import izip ImportError: cannot import name 'izip'  the built-in zip seems the only choice. Commented Jun 22, 2015 at 18:46
• You should islice as well, to avoid the creation of a list copy. Commented Jun 22, 2015 at 19:30
• @jonrsharpe Yep, that'd also be a good idea... Commented Jun 22, 2015 at 19:42