Python Sorting Algorithms

A key function takes one item and returns the value to compare. Python calls it once per item:

crews = [("Herons", 83.4, "B"), ("Otters", 79.1, "A"), ("Kites", 91.0, "A")]
by_time = sorted(crews, key=lambda c: c[1])                 # fastest first
slowest_first = sorted(crews, key=lambda c: c[1], reverse=True)
by_division_then_time = sorted(crews, key=lambda c: (c[2], c[1]))

Returning a tuple sorts by several fields: first by division, then by time within each division. operator.itemgetter(1) and operator.attrgetter("time") are faster, readable alternatives to simple lambdas.

The sort is only as correct as its key. Sorting regatta results by crew name produces a perfectly sorted list that answers the wrong question. Watch for keys that compare in an unexpected way, such as times stored as text: "9:58" > "10:02" because strings compare character by character. Convert to numbers first, or use a key like key=lambda s: tuple(map(int, s.split(":"))).

A sort is stable if items with equal keys keep their original relative order. Python's sort is guaranteed stable:

results = [("Herons", 83), ("Otters", 79), ("Swifts", 83)]
print(sorted(results, key=lambda r: r[1]))
# Herons stays before Swifts: both 83, Herons came first in the input

Stability lets you build multi-level sorts in passes: sort by the secondary key first, then by the primary key, and ties in the primary key stay ordered by the secondary one. Sorting by a tuple key achieves the same in one pass.

Stability doesn't decide ties for you. If the input order was arbitrary, such as the order crews registered, the tie order is arbitrary too. When ties matter, as they do for medals, add an explicit tie-breaker to the key, such as the final split time or lane number, so the ranking is deterministic and explainable.

Insertion sort builds a sorted prefix, taking each new item and shifting larger items right until it fits:

def insertion_sort(items):
    items = list(items)
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = current
    return items

It's O(n²) in the worst case (reversed input) but O(n) on nearly sorted data, uses O(1) extra space and is stable.

Merge sort splits the list in half, sorts each half recursively, and merges the two sorted halves by repeatedly taking the smaller front item:

def merge_sort(items):
    if len(items) <= 1:
        return list(items)
    middle = len(items) // 2
    left, right = merge_sort(items[:middle]), merge_sort(items[middle:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # <= keeps it stable
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

It's O(n log n) in every case and stable, but needs O(n) extra space. Python's Timsort combines both ideas: it finds already-sorted runs, extends short ones with insertion sort and merges runs, which is why it's very fast on real-world data that's partly ordered.

podium = sorted(results, key=lambda r: r[1])[:3]
import heapq
fastest_three = heapq.nsmallest(3, results, key=lambda r: r[1])

Use sorted() when you need to keep the original order too, and list.sort() to sort a list you own in place. When you only need the top few items from a large collection, heapq.nsmallest and nlargest avoid sorting everything, and min()/max() find a single extreme in O(n).

Implementing your own sort is for learning; in application code the built-in is faster, stable and thoroughly tested. Your job is to supply the right key and tie-breakers.

Task: trace insertion and merge sorting, then use a stable key-based sort for tied race results.

results = [("Herons", 83, 3), ("Otters", 79, 1), ("Swifts", 83, 2), ("Kites", 91, 4)]

# Stable sort: ties keep registration order
print([name for name, t, lane in sorted(results, key=lambda r: r[1])])
# ['Otters', 'Herons', 'Swifts', 'Kites']

# Explicit tie-breaker: lower lane number wins a tie
print([name for name, t, lane in sorted(results, key=lambda r: (r[1], r[2]))])
# ['Otters', 'Swifts', 'Herons', 'Kites']

Trace merge sort on [83, 79, 83, 91] on paper: split into [83, 79] and [83, 91], sort each to [79, 83] and [83, 91], then merge to [79, 83, 83, 91], taking from the left half on ties. For the worked check, a stable sort preserves the original relative order of items with equal keys.

The Python Sorting HOW TO covers keys, stability and multi-level sorts. Continue with stacks and queues and revisit complexity. Practise with the Python exercises and Python quiz.