Is the list sorted?

Question

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]))

Answer 1

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))

Answer 2

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