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])
    >>> is_sorted([1, 2, 7, 3])
    return all(curr <= list_[index + 1]
                  for index, curr in enumerate(list_[:-1]))
  • \$\begingroup\$ 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. \$\endgroup\$
    – jonrsharpe
    Commented Jun 22, 2015 at 17:57
  • \$\begingroup\$ @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. :) \$\endgroup\$
    – Caridorc
    Commented Jun 22, 2015 at 17:58
  • \$\begingroup\$ Well, maybe. O(2n) is still O(n), after all. But there are fixed costs to consider too. \$\endgroup\$
    – jonrsharpe
    Commented Jun 22, 2015 at 18:01
  • 2
    \$\begingroup\$ "pythonic way to check if a list is sorted or not": stackoverflow.com/questions/3755136/… \$\endgroup\$ Commented Jun 22, 2015 at 20:22

2 Answers 2


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.

    itertools.izip as zip
except ImportError:
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))
  • \$\begingroup\$ Instead of tee you could use the builtin iter in a similar way: list2 = iter(mylist); next(list2) \$\endgroup\$ Commented Jun 23, 2015 at 5:44
  • \$\begingroup\$ Yes, if you are sure you will only ever have certain types. Assuming the data type isn't really idiomatic, though. \$\endgroup\$ 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:

    from itertools import izip
except ImportError:
    izip = zip
  • \$\begingroup\$ No need for a special case, it already works for zero and one elements. \$\endgroup\$
    – Caridorc
    Commented Jun 22, 2015 at 18:45
  • \$\begingroup\$ 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. \$\endgroup\$
    – Caridorc
    Commented Jun 22, 2015 at 18:46
  • 3
    \$\begingroup\$ You should islice as well, to avoid the creation of a list copy. \$\endgroup\$
    – jonrsharpe
    Commented Jun 22, 2015 at 19:30
  • \$\begingroup\$ @jonrsharpe Yep, that'd also be a good idea... \$\endgroup\$
    – Yuushi
    Commented Jun 22, 2015 at 19:42

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.