Sorting, Key Functions, bisect & heapq

Algorithmic performance in Python relies heavily on C-accelerated searching and sorting primitives. Timsort (list.sort(), sorted()), Binary Search (bisect), and Priority Queues (heapq) provide sub-linear and logarithmic operations when handling large datasets.

This chapter details Timsort key-function optimization, binary search insertion via bisect, Min-Heap binary array representations (heapq), and top-K selection performance.

1. Timsort & Key-Function Mechanics (list.sort() / sorted())

Python’s default sorting algorithm is Timsort—an adaptive, stable hybrid merge/insertion sort algorithm operating in $O(N \log N)$ worst-case time and $O(N)$ best-case time for pre-sorted arrays.

Key Function Optimization:

When sorting using key=fn (e.g. sorted(users, key=lambda u: u.age)):

1. Single Evaluation: The key function is evaluated exactly once per item (Dschwartzian Transform).
2. Tuple Comparison: CPython builds a temporary array of (key_value, original_item) tuples and sorts them in native C memory, avoiding Python function callback overhead during comparisons.

# Sort complex objects by multi-attribute tuple priority
users.sort(key=lambda u: (-u.score, u.name)) # Score descending, Name ascending

2. Fast Binary Search with bisect

The bisect module implements binary search on pre-sorted sequences in $O(\log N)$ time:

• bisect_left(a, x): Returns the leftmost insertion index for x to maintain sorted order.
• bisect_right(a, x): Returns the rightmost insertion index for x.
• insort(a, x): Finds insertion index via binary search and executes a.insert(idx, x).

import bisect

# Grade lookup using boundary thresholds
cutoffs = [60, 70, 80, 90]
grades = ["F", "D", "C", "B", "A"]

def get_grade(score: int) -> str:
    idx = bisect.bisect_right(cutoffs, score)
    return grades[idx]

print(get_grade(85))  # Returns "B" in O(log N) time!

3. Priority Queues with heapq (Min-Heap)

The heapq module implements a Min-Heap algorithm using standard 0-indexed Python lists, where heap[0] is guaranteed to be the smallest item.

Min-Heap Array Binary Tree Mapping:

Array Index:  [ 10,  20,  15,  30,  40 ]
Index Map:       0    1    2    3    4

Tree Structure:
                    [ 10 ] (index 0)
                   /      \
      (index 1) [ 20 ]   [ 15 ] (index 2)
                /   \
  (index 3) [ 30 ] [ 40 ] (index 4)

Parent/Child Index Math:
 - Left Child Index  = 2 * i + 1
 - Right Child Index = 2 * i + 2
 - Parent Index      = (i - 1) // 2

Core Operations:

• heapq.heappush(heap, item): Inserts item and restores min-heap invariant in $O(\log N)$ time.
• heapq.heappop(heap): Pops and returns smallest item (heap[0]) in $O(\log N)$ time.
• heapq.heapify(list): Converts a list into a min-heap in-place in $O(N)$ linear time.

4. Top-K Selection Performance (nlargest vs nsmallest)

Finding the top $K$ largest elements from an $N$-item list can be achieved via multiple approaches:

1. Full Sort (sorted(arr)[-K:]): $O(N \log N)$ time. Allocates full sorted list.
2. Min-Heap Selection (heapq.nlargest(K, arr)): $O(N \log K)$ time. Maintains a heap of size $K$, skipping full array sorting.

Rule of Thumb: Use heapq.nlargest when $K \ll N$ (e.g. top 10 items out of 1,000,000). If $K \approx N$, full sorted() in C is faster due to lower constant overhead.