Python's built-in sort (Timsort)

Why it costs this much

Timsort merges runs of already-ordered data, so nearly sorted input is fast and the worst case is still O(n log n).

Code

items.sort()                        # O(n log n) worst case, stable
items.sort(key=lambda p: p[1])      # key is computed once per element
ordered = sorted(items)             # returns a new list: O(n) extra space

Common pitfalls

Sorting costs O(n log n), which dominates any linear pass that follows. The key function runs once per element.

Operation by operation

Built-in sort (Python sorted, list.sort). Timsort. Stable. Runs of already-sorted data are detected. Java sorts objects with the same Timsort idea and primitives with dual-pivot quicksort. JavaScript Array.sort is stable since ES2019.