How do I check if a list is sorted?

Question

In python, how do I test whether a list of numbers is already sorted or not?

Answer 1

This is only possible by iterating over the list (implicitly or explicitly):

all(b >= a for a, b in zip(the_list, the_list[1:])

But why not just sort it if you need it to be sorted? Python's sorting algorithm will be really cheap on an already sorted list -- possibly cheaper than the test above.

EDIT: Because this turned into a discussion about performance, here is a version using lazy iterators:

it = iter(the_list)
it.next()
all(b >= a for a, b in itertools.izip(the_list, it))

For a randomly ordered list with a million entries, this is more than 10000 times faster than the_list == sorted(the_list).

Answer 2

some_list == sorted(some_list)

Answer 3

Normally you should already know if a list is sorted (because that's how your input is defined, or you previously sorted it).

If you need to verify if a list is sorted because, if it's not, you want to sort it, just sort it. It's a cheap operation if the list is already sorted, and not a lot more expensive than verifying the order explicitly.

In other words:

mylist.sort()

now you know it's sorted.

Answer 4

More a comment on the other answers than an answer, but this site makes proper comments impossible.

The sort solutions are faster if the list is already partially or fully sorted. The iterative solutions are faster if the list is likely to be in random order, or if the list is out of order early on.

This is for two reasons. First, Python's sort is very good when it's given data in an order it understands (partially sorted, reversed, etc), but if the data is random or otherwise unpredictable then it can do no better than any other sort. Second, the iterative solution can short circuit doing next to no work, if it finds early on that the list is unsorted.

This shows the opposite extremes:

import timeit, random, itertools

def a(data):
    return all(b >= a for a, b in itertools.izip(data, itertools.islice(data, 1, None)))

def b(data):
    return data == sorted(data)

def main():
    data = range(1000000)
    print "Sorted, iterative:", timeit.timeit(lambda: a(data), number=10)
    print "Sorted, sort:", timeit.timeit(lambda: b(data), number=10)

    random.shuffle(data)
    print "Random, iterative:", timeit.timeit(lambda: a(data), number=10)
    print "Random, sort:", timeit.timeit(lambda: b(data), number=10)

resulting in these timings on my system:

Sorted, iterative: 1.42838597298
Sorted, sort: 0.498414993286
Random, iterative: 0.000043
Random, sort: 10.5548219681

So, at these extremes the sorting approach is about three times faster, and the linear approach is about ... two hundred thousand times faster.

Note that the real difference here is not O(n) vs. O(n log n); the difference between those complexities isn't nearly that wide. The main difference is that the linear version can short circuit as soon as it finds two values that are out of order, where the sorting version always has to do all of the work.

A native implementation could get ideal performance of both, giving O(n) complexity, the ability to short-circuit, and the low overhead of native code that makes the sorting approach faster. If (and only if!) performance really matters, that would be the correct solution.

(Note that normally I wouldn't recommend choosing a solution based on performance unless performance was actually an issue, but it's worth noting here since neither approach is that much simpler than the other. The sorting version is a little simpler to understand, but there's nothing at all complex about the iterative version either.)

Answer 5

if L == (lambda pp=[]: reduce(lambda p, i: pp.append(reduce(lambda t, i:
        (lambda t, i, j: (lambda l=[]: map(lambda x: (lambda xx=l.append(1):
        t[sum(l) - 1] if sum(l) not in map(1..__radd__, (i, j)) else (t[i] if
        sum(l) == j + 1 else t[j]))(), t))())(t, i, i + 1) if t[i] >= t[i + 1]
        else t, xrange(len(p) - 1), p)) or pp[-1], iter(lambda: len(pp) >= 2
        and list.__eq__(*pp[-2:]), True), L))():
    print "yeah, it's sorted"