Кроме скорости, сортировку описывают её свойства. Они определяют, подходит ли алгоритм задаче: сортировка таблицы по нескольким столбцам, сортировка огромных данных при малой памяти, работа с почти отсортированным входом.

Устойчивая и неустойчивая сортировка по числу
Устойчивая и неустойчивая сортировка по числу

Постановка задачи и компаратор

Даны элементы и правило сравнения (функция-ключ или компаратор). Нужно расставить их так, чтобы каждая соседняя пара удовлетворяла a <= b. Два разных элемента могут быть равны по ключу, например два человека из одного города.

Устойчивость

Сортировка устойчива, если равные элементы сохраняют исходный взаимный порядок. Сортировка выбором неустойчива: её дальние обмены перепрыгивают через равные элементы. sorted и list.sort устойчивы.

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