Besides speed, a sorting algorithm is described by its properties. They decide whether it fits a task: sorting a table by several columns, sorting huge data with little memory, handling nearly sorted input.

Stable vs unstable sort by the number
Stable vs unstable sort by the number

The problem and the comparator

Given elements and a comparison rule (a key function or a comparator), arrange them so that every neighbouring pair satisfies a <= b. Two different elements can be equal by the key, for example two people from the same city.

Stability

A sort is stable if equal elements keep their original relative order. Selection sort is unstable: its long swaps jump over equal elements. sorted and list.sort are stable.

python
def selection_sort(items):
    a = list(items)
    for i in range(len(a) - 1):
        m = min(range(i, len(a)), key=lambda j: a[j][0])
        a[i], a[m] = a[m], a[i]
    return a