Что такое стабильность сортировки и какие сортировки стабильны?

Стабильная сортировка сохраняет относительный порядок элементов с равными ключами; это критично при сортировке по нескольким полям подряд.

Пример

Сортируем сотрудников сначала по имени, затем стабильно по отделу — внутри отдела имена останутся по алфавиту. Нестабильная сортировка этот порядок разрушит.

Какие алгоритмы стабильны

• Стабильны: merge sort, insertion sort, bubble sort, counting sort в аккуратной реализации, Timsort.
• Нестабильны: quicksort, heapsort, selection sort.

Как сделать нестабильную сортировку стабильной

Добавить к ключу исходный индекс: сортировать пару (значение, индекс) — равные значения разрешатся по индексу. Цена — O(n) дополнительной памяти.

Где это важно

• UI-таблицы: пользователь кликает по колонкам и ждёт сохранения предыдущего порядка.
• Многоступенчатая сортировка записей в отчётах.

Коротко для собеседования

Стабильная сортировка не переставляет элементы с равными ключами, поэтому сортировки по нескольким полям можно применять последовательно. Это важно для UI-таблиц и отчётов; в JS Array.prototype.sort стабилен начиная с ES2019, а нестабильный алгоритм исправляют добавлением индекса к ключу.