Sorting in Python

Python gives you two complementary sorting tools — list.sort() which sorts in place, and the built-in sorted() which returns a brand-new list — plus two powerful stdlib modules, bisect and heapq, for maintaining ordered sequences efficiently.

---

list.sort() vs sorted()

list.sort() mutates the list and returns None. sorted() accepts any iterable and always returns a new list.

Rule of thumb: use .sort() when you own the list and want zero overhead; use sorted() when you need to preserve the original or are working with arbitrary iterables.

---

The key= Parameter

Both sort() and sorted() accept a key argument — a callable that extracts the comparison value from each element. Python calls it once per element (not once per comparison), so it's O(n) overhead rather than O(n log n).

---

operator.attrgetter and operator.itemgetter

The operator module provides pre-built key functions that are typically faster than equivalent lambdas because they're implemented in C.

---

reverse=True

Pass reverse=True to either sort() or sorted() to sort in descending order. This is slightly more efficient than reversing a sorted result because it avoids a second pass.

---

Multi-Level Sort (Tuple Keys)

Return a tuple from the key function to sort by multiple criteria. Python compares tuples element-by-element, falling through to the next element when earlier ones are equal.

You can only negate numeric keys. For strings, a common trick is a wrapper class that reverses the comparison, but multi-level string sorts usually just use two separate stable sorts (see below).

---

Stability Guarantee

Python's sort is stable: equal elements retain their original relative order. This enables the "sort by lowest priority first, then sort by highest priority" idiom:

---

bisect — Maintaining Sorted Order

The bisect module implements binary search on an already-sorted list. It avoids the need to re-sort after every insertion, giving O(log n) search and O(n) insertion.

When to use bisect: maintaining a leaderboard, keeping a sorted event timeline, or any scenario where you insert into a sorted sequence far less often than you search it.

---

heapq — Priority Queue (Min-Heap)

heapq implements a min-heap over a plain Python list. The smallest element is always at index 0. All operations are O(log n) except heapify which is O(n).

nlargest and nsmallest

For very small n (top-3 out of millions), nlargest/nsmallest uses a heap and is faster than sorting. For large n, sorted() wins.

heapq with Tuples for Priority

Because heapq compares elements directly, tuples provide a natural way to attach priority to items. The first element is the sort key:

---

When to Use Each