TimSort (Гибридная сортировка)
Краткое описание
Гибридный адаптивный алгоритм сортировки, созданный Тимом Петерсом для Python в 2001. Комбинирует Merge Sort и Insertion Sort, анализируя структуру данных и находя уже отсортированные последовательности (runs). Используется по умолчанию в Python, Java, Android. Стабильный, эффективен на реальных данных, имеет O(n) на почти отсортированных данных.
Когда использовать
- Реальные данные — оптимизирован для данных из реального мира, которые часто частично отсортированы
- Нужна стабильность — всегда стабильный алгоритм
- Производственный код — используется в стандартных библиотеках множества языков
- Почти отсортированные данные — деградирует до O(n) на уже отсортированных данных
- Данные с паттернами — находит и использует уже отсортированные подпоследовательности
- Универсальный выбор — хорошо работает на любых типах данных
Когда не стоит использовать:
- Ограниченная память — требует O(n) дополнительной памяти
- Маленькие массивы — накладные расходы на анализ данных не окупятся
- Сложность реализации — один из самых сложных алгоритмов для понимания и имплементации
С объяснением логики работы
/**
* TimSort — упрощённая учебная версия
*
* Реальный TimSort намного сложнее с множеством оптимизаций.
* Здесь показаны основные идеи алгоритма.
*
* Принцип:
* 1. Делим массив на небольшие части (runs) размером minrun (32-64)
* 2. Сортируем каждую часть Insertion Sort (эффективен на малых массивах)
* 3. Сливаем части используя Merge Sort
* 4. Используем galloping mode для оптимизации слияния
*/
// Минимальный размер run (в реальном TimSort вычисляется динамически)
const MIN_MERGE = 32;
/**
* Вычисление minrun на основе размера массива
* Цель: сделать так, чтобы n/minrun было степенью 2 или близко к ней
*/
function getMinrun(n) {
let r = 0;
while (n >= MIN_MERGE) {
r |= n & 1; // Запоминаем, было ли нечётное
n >>= 1; // Делим на 2
}
return n + r;
}
/**
* Insertion Sort для малых подмассивов
* TimSort использует бинарный поиск для оптимизации, здесь упрощённая версия
*/
function insertionSort(arr, left, right) {
for (let i = left + 1; i <= right; i++) {
const key = arr[i];
let j = i - 1;
// Сдвигаем элементы, пока не найдём место для key
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
/**
* Слияние двух отсортированных подмассивов
* В реальном TimSort здесь используется galloping mode
*/
function merge(arr, left, mid, right) {
// Копируем левую часть
const leftPart = arr.slice(left, mid + 1);
// Копируем правую часть
const rightPart = arr.slice(mid + 1, right + 1);
let i = 0; // Индекс для leftPart
let j = 0; // Индекс для rightPart
let k = left; // Индекс для arr
// ОСНОВНОЕ СЛИЯНИЕ
// Сравниваем элементы и выбираем меньший
while (i < leftPart.length && j < rightPart.length) {
// <= обеспечивает стабильность
if (leftPart[i] <= rightPart[j]) {
arr[k++] = leftPart[i++];
} else {
arr[k++] = rightPart[j++];
}
}
// Копируем оставшиеся элементы
while (i < leftPart.length) {
arr[k++] = leftPart[i++];
}
while (j < rightPart.length) {
arr[k++] = rightPart[j++];
}
}
/**
* Основная функция TimSort (упрощённая)
*/
function timSort(arr) {
const n = arr.length;
const minrun = getMinrun(n);
// ШАГ 1: Сортируем индивидуальные runs размером minrun
// Используем Insertion Sort, так как он эффективен на малых массивах
for (let start = 0; start < n; start += minrun) {
const end = Math.min(start + minrun - 1, n - 1);
insertionSort(arr, start, end);
}
// ШАГ 2: Начинаем сливать отсортированные runs
// Размер сливаемых частей удваивается на каждой итерации
let size = minrun;
while (size < n) {
// Выбираем начальную точку левого подмассива
for (let start = 0; start < n; start += 2 * size) {
// Находим конечную точку левого подмассива
// mid+1 — начало правого подмассива
const mid = Math.min(start + size - 1, n - 1);
// Находим конечную точку правого подмассива
const end = Math.min(start + 2 * size - 1, n - 1);
// Сливаем подмассивы arr[start...mid] и arr[mid+1...end]
if (mid < end) {
merge(arr, start, mid, end);
}
}
// Увеличиваем размер вдвое для следующей итерации
size *= 2;
}
return arr;
}
// Пример использования
const numbers = [5, 21, 7, 23, 19, 10, 2, 15, 8, 13];
console.log("Исходный массив:", numbers);
timSort(numbers);
console.log("Отсортированный массив:", numbers);
/**
* Что происходит в реальном TimSort (но не реализовано здесь):
*
* 1. ОБНАРУЖЕНИЕ ЕСТЕСТВЕННЫХ RUNS
* TimSort ищет уже отсортированные последовательности в массиве.
* Если находит убывающую последовательность — разворачивает её.
*
* 2. GALLOPING MODE (режим галопирования)
* При слиянии, если элементы из одного массива идут подряд,
* TimSort переключается в режим бинарного поиска для ускорения.
*
* 3. УМНОЕ УПРАВЛЕНИЕ СТЕКОМ
* TimSort поддерживает стек runs и сливает их по определённым правилам:
* - |Z| > |Y| + |X|
* - |Y| > |X|
* где X, Y, Z — три верхних элемента стека
*
* 4. БИНАРНЫЙ INSERTION SORT
* Вместо линейного поиска места вставки, используется бинарный поиск
*/С анализом сложностей
/**
* TimSort с анализом сложности
*
* ВРЕМЕННАЯ СЛОЖНОСТЬ:
* - Лучший случай: O(n) — массив уже отсортирован или почти отсортирован
* - Средний случай: O(n log n) — стандартные данные
* - Худший случай: O(n log n) — гарантированная верхняя граница
*
* ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
* - O(n) — требуется дополнительная память для слияния
*
* ОСОБЕННОСТИ:
* - Адаптивный: использует существующий порядок в данных
* - Стабильный: всегда сохраняет порядок равных элементов
* - Производственный: используется в Python, Java, Android, V8
* - Сложный: один из самых сложных алгоритмов сортировки
*/
const MIN_MERGE = 32;
function getMinrun(n) {
// O(log n) — количество делений на 2
let r = 0;
while (n >= MIN_MERGE) {
r |= n & 1;
n >>= 1;
}
return n + r;
}
function insertionSort(arr, left, right) {
// ВРЕМЕННАЯ СЛОЖНОСТЬ для одного run:
// - Лучший случай: O(right - left) если данные отсортированы
// - Худший случай: O((right - left)²) если обратный порядок
//
// Но так как run небольшой (≤64 элемента), это эффективно
// O(64²) = O(4096) = O(1) константное время для фиксированного minrun
for (let i = left + 1; i <= right; i++) {
const key = arr[i];
let j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
function merge(arr, left, mid, right) {
// ВРЕМЕННАЯ СЛОЖНОСТЬ: O(right - left + 1)
// Каждый элемент обрабатывается ровно один раз
//
// ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ: O(right - left + 1)
// Создаём копии для слияния
const leftPart = arr.slice(left, mid + 1); // O(mid - left + 1)
const rightPart = arr.slice(mid + 1, right + 1); // O(right - mid)
let i = 0, j = 0, k = left;
// O(leftPart.length + rightPart.length) = O(right - left + 1)
while (i < leftPart.length && j < rightPart.length) {
if (leftPart[i] <= rightPart[j]) {
arr[k++] = leftPart[i++];
} else {
arr[k++] = rightPart[j++];
}
}
while (i < leftPart.length) arr[k++] = leftPart[i++];
while (j < rightPart.length) arr[k++] = rightPart[j++];
}
function timSort(arr) {
const n = arr.length;
const minrun = getMinrun(n); // O(log n)
// ФАЗА 1: СОЗДАНИЕ И СОРТИРОВКА RUNS
//
// ВРЕМЕННАЯ СЛОЖНОСТЬ:
// - Количество runs: ⌈n / minrun⌉ ≈ n/32 до n/64
// - Сортировка одного run: O(minrun²) для insertion sort
// - Но minrun — константа (≤64), поэтому O(1) на run
// - Итого: (n / minrun) * O(minrun²) = n * O(minrun) = O(n)
//
// ЛУЧШИЙ СЛУЧАЙ (уже отсортирован):
// - Insertion sort на отсортированных данных: O(minrun)
// - Итого: (n / minrun) * O(minrun) = O(n)
for (let start = 0; start < n; start += minrun) {
const end = Math.min(start + minrun - 1, n - 1);
insertionSort(arr, start, end);
}
// ФАЗА 2: СЛИЯНИЕ RUNS (аналогично Merge Sort)
//
// ВРЕМЕННАЯ СЛОЖНОСТЬ: O(n log(n/minrun))
// - Количество уровней слияния: log₂(n/minrun)
// - Работа на каждом уровне: O(n)
// - Итого: O(n log(n/minrun))
//
// Если minrun = 32:
// O(n log(n/32)) = O(n (log n - log 32))
// = O(n log n - 5n)
// = O(n log n)
let size = minrun;
while (size < n) {
// Внутренний цикл обрабатывает все элементы: O(n)
for (let start = 0; start < n; start += 2 * size) {
const mid = Math.min(start + size - 1, n - 1);
const end = Math.min(start + 2 * size - 1, n - 1);
if (mid < end) {
// Каждый merge обрабатывает (end - start + 1) элементов
// Суммарно на уровне: O(n)
merge(arr, start, mid, end);
}
}
size *= 2;
}
// ОБЩАЯ СЛОЖНОСТЬ:
// O(n) [создание runs] + O(n log n) [слияние] = O(n log n)
//
// НО в лучшем случае (отсортированные данные):
// - Создание runs: O(n)
// - Слияние: данные уже в порядке, минимальная работа
// - Итого: O(n)
return arr;
}
// ПОЧЕМУ TIMSORT БЫСТРЕЕ НА ПРАКТИКЕ:
//
// 1. АДАПТИВНОСТЬ
// На почти отсортированных данных: O(n)
// На полностью случайных данных: O(n log n)
// Реальные данные часто частично упорядочены
//
// 2. ИСПОЛЬЗОВАНИЕ INSERTION SORT
// Для малых подмассивов insertion sort быстрее merge sort
// из-за меньших накладных расходов и лучшей cache locality
//
// 3. GALLOPING MODE (не реализован здесь)
// При слиянии, если один массив "выигрывает" много раз подряд,
// переключается на бинарный поиск вместо линейного сравнения
//
// 4. УМНОЕ УПРАВЛЕНИЕ ПАМЯТЬЮ
// Merge выполняется только для меньшей части,
// что экономит память
//
// СРАВНЕНИЕ С ДРУГИМИ АЛГОРИТМАМИ:
//
// TimSort vs Merge Sort:
// ✓ TimSort адаптивный: O(n) на отсортированных
// ✓ TimSort использует insertion sort для малых массивов
// ✗ TimSort сложнее реализовать
// = Оба O(n log n) в худшем случае
// = Оба стабильные
// = Оба требуют O(n) памяти
//
// TimSort vs Quick Sort:
// ✓ TimSort стабильный
// ✓ TimSort гарантирует O(n log n)
// ✓ TimSort быстрее на частично отсортированных данных
// ✗ TimSort требует O(n) памяти vs O(log n) у Quick Sort
// ✗ Quick Sort быстрее на полностью случайных данных
//
// КОГДА ИСПОЛЬЗОВАТЬ TIMSORT:
// ✓ Производственный код общего назначения
// ✓ Данные из реального мира (часто частично упорядочены)
// ✓ Нужна стабильность
// ✓ Нужна гарантированная O(n log n) производительность
// ✗ Ограниченная память (используйте Heap Sort или Quick Sort)
// ✗ Нужна простая реализация (используйте Merge Sort)
// Примеры производительности:
// ЛУЧШИЙ СЛУЧАЙ: O(n) — отсортированный массив
const best = [1, 2, 3, 4, 5, 6, 7, 8];
// TimSort обнаружит один большой run и почти ничего не сделает
// ПОЧТИ ОТСОРТИРОВАННЫЙ: O(n) или близко к O(n)
const nearSorted = [1, 2, 3, 5, 4, 6, 7, 8, 10, 9];
// Найдёт большие отсортированные runs, минимум работы
// ХУДШИЙ СЛУЧАЙ: O(n log n) — случайный порядок
const worst = [5, 2, 8, 1, 9, 3, 7, 4, 6];
// Работает как оптимизированный merge sort