Что такое стабильность строго

Формально: для алгоритма sort и ключа key, если в исходном массиве i < j и key(arr[i]) == key(arr[j]), то после sort(arr, key=key) в новых индексах эти элементы должны идти в том же порядке: тот, что был раньше в исходном, остаётся раньше в выходе.

Пример:

records = [
    ("Анна",   30),
    ("Иван",   25),
    ("Мария",  30),   # тот же возраст, что у Анны
    ("Олег",   25),   # тот же возраст, что у Ивана
]

stable_sorted = sorted(records, key=lambda r: r[1])
# [('Иван', 25), ('Олег', 25), ('Анна', 30), ('Мария', 30)]
# 25: Иван, Олег — порядок как в исходном
# 30: Анна, Мария — порядок как в исходном

Если бы сортировка была нестабильной, могло бы получиться [(Олег, 25), (Иван, 25), ...] — обмен между равными по возрасту. Для записей с дополнительными полями это разрушительно.

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

Главный вывод: большинство встроенных стабильных сортировок — это варианты merge или Timsort. Python sorted()/list.sort(), Java Arrays.sort для объектов, JavaScript Array.sort с 2018 — Timsort. C++ std::stable_sort — merge sort.

Зачем стабильность важна

Случай 1: сортировка по нескольким ключам

Допустим, нужно отсортировать сотрудников сначала по фамилии, потом по имени (внутри одной фамилии — по имени).

С stable sort можно сделать двумя проходами:

employees = [
    {"first": "Иван",   "last": "Петров"},
    {"first": "Анна",   "last": "Иванов"},
    {"first": "Иван",   "last": "Иванов"},
    {"first": "Олег",   "last": "Петров"},
]

# 1) сначала по имени
step1 = sorted(employees, key=lambda e: e["first"])
# 2) затем по фамилии (стабильно — порядок по имени сохранится для равных фамилий)
result = sorted(step1, key=lambda e: e["last"])

for r in result:
    print(r)
# {'first': 'Анна', 'last': 'Иванов'}
# {'first': 'Иван', 'last': 'Иванов'}
# {'first': 'Иван', 'last': 'Петров'}
# {'first': 'Олег', 'last': 'Петров'}

Внутри одной фамилии порядок по имени сохранён (Анна, Иван у Ивановых; Иван, Олег у Петровых). Это и есть multi-key sort через stability.

С нестабильной сортировкой так делать нельзя — нужно бы написать compound key ((last, first)), что не всегда удобно (например, разные направления сортировки).

Случай 2: сортировка с тайбрейкером

Иногда главный ключ имеет повторы, и хочется тайбрейкер по другому ключу:

events = [
    {"ts": 100, "user": "A"},
    {"ts": 200, "user": "B"},
    {"ts": 100, "user": "C"},
]

# хотим: по ts (главное), при равенстве — по user
result = sorted(events, key=lambda e: (e["ts"], e["user"]))

Это работает без stability — тайбрейкер встроен в ключ. Stability нужна, когда тайбрейкер — это исходный порядок (т.е. «при равенстве сохранить как было»). Тогда compound key не нужен, достаточно stable sort по основному ключу.

Случай 3: pandas multi-column sort

import pandas as pd
df.sort_values(["country", "age"])     # stable, multi-column

Pandas использует stable sort (Timsort/numpy) — порядок внутри group сохраняется. Это критично для воспроизводимости при выборе «топ-N» в каждой группе и т.д.

Случай 4: SQL ORDER BY

SELECT * FROM employees ORDER BY salary DESC;

Стандарт SQL не гарантирует стабильности (в разных СУБД по-разному). PostgreSQL, MySQL могут вести себя по-разному. Если важно — добавляйте секунда ключ:

SELECT * FROM employees ORDER BY salary DESC, id;

id действует как разрыв связей. Это compound key — работает даже на нестабильных сортировках.

Stability в Quick-sort можно?

Можно — за дополнительную память. Идея: вместо in-place partition использовать копирование с сохранением order:

def stable_quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]   # фиксированный pivot
    less = [x for x in arr[1:] if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return stable_quicksort(less) + equal + stable_quicksort(greater)

Это stable: list comprehension сохраняет order. Но это не in-place и в Python медленнее обычного quicksort. На практике stable quicksort встречается редко — проще использовать merge или Timsort.

DE-кейс: ranking with tiebreaker

Сценарий: вывести список пользователей по revenue (по убыванию), при равенстве — по дате регистрации (более ранние раньше).

С stable sort:

# 1) сначала по дате регистрации (вторичный ключ)
users.sort(key=lambda u: u["registered_at"])
# 2) затем по revenue (основной ключ, descending)
users.sort(key=lambda u: u["revenue"], reverse=True)

Stable sort гарантирует, что для одинакового revenue порядок по date регистрации (первая сортировка) сохранится.

С compound key:

users.sort(key=lambda u: (-u["revenue"], u["registered_at"]))

Один вызов, тот же результат. Удобнее, читабельнее, не требует stability как таковой (хотя обычно она есть).

DE-кейс: дедупликация с keep first

import pandas as pd

df = pd.DataFrame({...})

# сохранить только последнюю запись для каждого user_id
df_sorted = df.sort_values("ts")       # stable sort
df_dedup = df_sorted.drop_duplicates("user_id", keep="last")

drop_duplicates с keep="last" оставляет последнее вхождение. Stable sort гарантирует, что «последнее по ts» — это действительно последняя запись по времени. Без stability порядок внутри одного ts мог бы быть разный — результат недетерминированный.

DE-кейс: пакетная обработка с порядковыми номерами

Поток событий приходит в каком-то порядке, у каждого есть seq_no. Нужно сортировать по ts, но при равенстве — по seq_no (исходный порядок прихода).

# вариант 1: stable sort с key=ts (seq_no был исходным порядком)
events.sort(key=lambda e: e["ts"])

# вариант 2: compound key
events.sort(key=lambda e: (e["ts"], e["seq_no"]))

Вариант 1 работает, если исходный порядок events совпадает с порядком seq_no. Иначе — compound. На практике лучше compound — не зависит от того, как именно был создан список.

Когда стабильность не важна

• Простая сортировка одного ключа без повторов или с unique значениями. Стабильность не наблюдается.
• Когда не важен порядок равных. Сортировка чисел для медианы — без разницы, какой из двух равных окажется первым.
• Когда нужна максимальная производительность на больших массивах — quicksort или introsort часто быстрее merge/Timsort на случайных данных.

В числовых вычислениях (NumPy, SciPy) часто используют unstable quicksort или introsort — для скорости. Если стабильность нужна, явно указывают kind="stable":

import numpy as np
arr = np.array([...])
arr_sorted = np.sort(arr, kind="stable")

Тест стабильности

Можно проверить, стабилен ли алгоритм, через массив из пар (key, original_index):

records = [(1, 0), (2, 1), (1, 2), (2, 3), (1, 4)]
sorted_by_key = sorted(records, key=lambda r: r[0])
# [(1, 0), (1, 2), (1, 4), (2, 1), (2, 3)]

# Проверка: для каждого key, второй элемент возрастает
ok = True
prev_key, prev_orig = None, -1
for key, orig in sorted_by_key:
    if key == prev_key and orig < prev_orig:
        ok = False
        break
    prev_key, prev_orig = key, orig

print("stable" if ok else "not stable")

Если алгоритм нестабилен — мы увидим, что original index «прыгает» для равных ключей.

Попробуй сам

Возьмите DataFrame:

import pandas as pd
df = pd.DataFrame({
    "country": ["RU", "FR", "RU", "FR", "RU", "DE"],
    "age": [30, 25, 25, 30, 35, 40],
    "name": ["A", "B", "C", "D", "E", "F"],
})

Задачи:

1. Отсортируйте сначала по age, потом по country, используя цепочку stable sort. Сравните результат с df.sort_values(["country", "age"]).
2. Найдите для каждой страны самого молодого человека (через sort + group + first).
3. Проверьте, что python sorted() стабилен через тест с парами (key, original_index).

В следующем уроке — in-place vs не in-place сортировки, и почему list.sort() отличается от sorted() в Python.