Emmimal P Alexander

Posted on Feb 17

Stop Sorting Just to Check Order: 5 Fast O(n) Methods in Python

#algorithms #beginners #tutorial #python

The Problem With Using sort() Just to Verify Order

A common mistake I see (and have made!):

Don't do this for validation

def is_sorted_bad(lst):
    return lst == sorted(lst)

Python's Timsort is O(n log n) and copies the whole list. For a million elements? ~20 million operations and extra memory — just for a yes/no! 😩
When the list is already sorted (often the case), it's pure waste.
Big O graph showing O(n log n) vs O(n)
Caption: Why sorting for verification hurts performance
The methods below are all O(n) with early exit — they stop at the first out-of-order pair.

Quick Note: What Does "Sorted" Mean?

Non-decreasing: Allows duplicates (<=) → [1, 2, 2, 3] ✅
Strictly increasing: No duplicates (<) → [1, 2, 2, 3] ❌

Same for descending (flip operators). All methods assume comparable elements.

Method 1: all() + zip() — The Go-To Pythonic Way 🔥

def is_sorted(lst):
    return all(x <= y for x, y in zip(lst, lst[1:]))

# Strictly increasing
def is_strictly_sorted(lst):
    return all(x < y for x, y in zip(lst, lst[1:]))

Lazy evaluation + early exit = super efficient.

Method 2: Classic For Loop — Interview Favorite

def is_sorted(lst):
    for i in range(len(lst) - 1):
        if lst[i] > lst[i + 1]:
            return False
    return True

Method 3: all() + range() — When You Need the Index

def is_sorted(lst):
    return all(lst[i] <= lst[i + 1] for i in range(len(lst) - 1))

Great for extensions like finding the first violation.

Method 4: itertools.pairwise() — Cleanest (Python 3.10+)

from itertools import pairwise

def is_sorted(lst):
    return all(x <= y for x, y in pairwise(lst))

No slice overhead — true O(1) space!

Method 5: operator.le — For Custom Objects

import operator

def is_sorted_by(lst, key):
    return all(key(x) <= key(y) for x, y in zip(lst, lst[1:]))

Perfect for sorting objects by attribute.

Descending Order? Just Flip It!

Ascending vs Descending

def is_non_increasing(lst):
    return all(x >= y for x, y in zip(lst, lst[1:]))

Edge Cases

Empty/single-element lists → Always True
Mixed types → TypeError (wrap in try/except)
None values → Handle manually

Performance Quick Comparison

Method	Time/Space Notes	Best For
all() + zip()	Readable, common	Everyday use
For loop	Clear, no tricks	Interviews
all() + range()	Useful when index is needed	Extensions (e.g., finding first violation)
pairwise()	True O(1) space	Modern Python (3.10+)
operator.le	Great for custom objects	Key-based or attribute sorting

NumPy/Pandas? Use Their Built-ins!

# NumPy
np.all(arr[:-1] <= arr[1:])

# Pandas
series.is_monotonic_increasing

When sort() Wins

If you need the sorted list anyway → Just call .sort() — Timsort is O(n) on sorted data!

That's it! Which method do you use most? Drop a comment below 👇
For the complete guide (with FAQs, full quiz, and more edge cases), head to my blog:
https://emitechlogic.com/check-if-list-is-sorted-python/

DEV Community