Introduction

Python sorted is built on Timsort, a hybrid algorithm designed for real world partially ordered data. It is stable, predictable, and usually fast for general purpose sorting. Understanding its complexity helps you reason about performance when lists become large.

Time Complexity of sorted

The typical time complexity is O(n log n), where n is the number of elements. This is the expected bound for comparison based sorting in the average and worst cases. Timsort can do better on partially sorted input because it detects natural runs and merges them efficiently.

Best case performance can approach linear behavior for already ordered or nearly ordered data. That is one reason Python sorting performs well in many production workloads where data has structure.

1def demo_basic_sort():
2    nums = [9, 1, 5, 3, 7, 2]
3    out = sorted(nums)
4    print(out)
5
6if __name__ == "__main__":
7    demo_basic_sort()

The algorithm also guarantees stability. If two items compare equal, their original relative order is preserved. Stability matters when you sort by multiple keys in stages.

Key Functions and Real Cost

When you pass key, Python evaluates that key once per element and caches results internally during sorting. This design avoids repeated key recomputation and improves efficiency.

1records = [
2    {"name": "Ana", "score": 90},
3    {"name": "Ben", "score": 90},
4    {"name": "Cara", "score": 85},
5]
6
7# Stable sort by score descending, then name ascending
8step1 = sorted(records, key=lambda r: r["name"])
9final = sorted(step1, key=lambda r: r["score"], reverse=True)
10
11for row in final:
12    print(row)

Complexity analysis should include key extraction cost. If key computation is expensive, total runtime can be dominated by that work rather than by comparisons. In those cases, precomputing keys explicitly or reducing conversion overhead can help.

Space Complexity and Memory Behavior

sorted returns a new list, so it uses additional memory. For very large data, memory footprint can become a limiting factor before raw CPU time does.

If mutating in place is acceptable, use list sort to avoid allocating a second full list object. The internal algorithm still needs temporary structures, but overall memory pressure is lower than creating a new sorted list from scratch.

items = [5, 3, 1, 4, 2]
items.sort()
print(items)

For streaming scenarios where full materialization is too expensive, consider alternatives such as heapq.nsmallest, chunked external sorting, or database level ordering.

Practical Benchmarking

If you need confident performance numbers, benchmark with representative data distributions:

• Random order
• Already sorted
• Reverse sorted
• Nearly sorted with small noise

1import random
2import time
3
4def benchmark(n=200000):
5    data = list(range(n))
6    random.shuffle(data)
7
8    t0 = time.perf_counter()
9    sorted(data)
10    t1 = time.perf_counter()
11
12    print(f"n={n}, seconds={t1 - t0:.4f}")
13
14if __name__ == "__main__":
15    benchmark()

Benchmark in the same runtime and hardware environment as production whenever possible. Microbenchmarks on a laptop can mislead if deployment workloads differ greatly.

Common Pitfalls

A common misconception is that Python always takes O(n log n) regardless of input order. Timsort can be faster on partially ordered data, so real runtime varies with structure.

Another pitfall is heavy key lambdas that perform parsing, regex, or network lookups. Sorting then appears slow even though comparison logic is fine. Keep keys cheap and deterministic.

Developers also chain multiple full sorts when one tuple key would do. Use a single key tuple when possible to reduce overhead and improve readability.

Finally, sorting huge lists without considering memory can trigger swap pressure or process instability. For very large datasets, use chunking or external systems designed for large scale ordering.

Summary

• Python sorted uses stable Timsort with typical O(n log n) complexity.
• Nearly sorted input can perform better due to run detection.
• Key extraction cost is part of total runtime and can dominate.
• sorted allocates a new list, while list sort mutates in place.
• Benchmark with realistic data shapes before optimizing.