Что такое устойчивая (стабильная) сортировка и когда это важно?

Если два элемента равны по ключу сортировки, но различаются другими полями, устойчивый алгоритм оставит их в том порядке, в котором они были. Неустойчивый может их переставить.

Когда это важно:

• сортировка по нескольким ключам по очереди. Нужно упорядочить сотрудников по отделу, а внутри отдела — по фамилии. Можно отсортировать по фамилии, а затем устойчиво по отделу: порядок фамилий внутри отдела сохранится;
• предсказуемый интерфейс. Пользователь кликает по столбцу таблицы — строки с одинаковым значением не должны «прыгать»;
• сортировка записей, у которых есть естественный порядок (по времени поступления).

Устойчивы: вставками, пузырьком, слиянием, Timsort (sorted в Python, Collections.sort и сортировка объектов в Java), подсчётом, поразрядная. Неустойчивы: быстрая, пирамидальная, выбором; Arrays.sort для примитивов в Java — но для чисел устойчивость и не имеет смысла.

Неустойчивый алгоритм можно сделать устойчивым, добавив к ключу исходный индекс — ценой памяти. Но проще сортировать по составному ключу сразу: key=lambda e: (e.dept, e.last_name).

people = [("Иванов", "продажи"), ("Петров", "ИТ"), ("Сидоров", "продажи"), ("Абрамов", "ИТ")]

by_name = sorted(people, key=lambda p: p[0])
by_dept = sorted(by_name, key=lambda p: p[1])   # устойчиво: внутри отдела — по фамилии
# [('Абрамов', 'ИТ'), ('Петров', 'ИТ'), ('Иванов', 'продажи'), ('Сидоров', 'продажи')]

sorted(people, key=lambda p: (p[1], p[0]))      # то же одним проходом