Как устроен
устойчивость
Статьи
SRT
Алгоритм
Простые сортировки
Вставки, выбор и пузырёк: квадратичные, но вставки работают внутри библиотечных сортировок.
O(n²)
2 задачи
SRT
Алгоритм
Сортировка слиянием
Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти.
O(n log n)
2 задачи
SRT
Алгоритм
Timsort
Находит готовые упорядоченные куски и сливает их: стек серий, галоп, powersort.
O(n log n), на готовых данных O(n)
2 задачи
SRT
Алгоритм
Сортировка подсчётом и поразрядная
Без сравнений: посчитать ключи или разложить их по цифрам — O(n + k) и O(d·n) вместо n log n.
O(n + k) и O(d·(n + b))
2 задачи
Задачи
Часто рядом
сортировка 4 классика 4 массив 3 собеседования 3 битовые трюки 2 в проде 2 на месте 1 разделяй и властвуй 1 рекурсия 1 внешняя память 1 амортизация 1 двоичный поиск 1