Сортировка Тимсорт: интерактивная анимация (Timsort)

// Полная рабочая реализация Timsort на C (с расчетом minrun)
#include <stdio.h>
#include <stdlib.h>

const int MIN_MERGE = 32; // Минимальный размер массива для слияния

// Функция вычисления оптимальной длины прогона (minrun)
// Делает так, чтобы (n / minrun) было степенью двойки или близко к ней
int calcMinRun(int n) {
    int r = 0;
    while (n >= MIN_MERGE) {
        r |= (n & 1); // Запоминаем, был ли сдвинут нечетный бит
        n >>= 1;      // Делим n на 2
    }
    return n + r;
}

// Сортировка вставками для коротких прогонов
void insertionSort(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int temp = arr[i]; // Берем текущий элемент
        int j = i - 1;
        // Сдвигаем все элементы, которые больше temp, вправо
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp; // Вставляем temp на освободившееся место
    }
}

// Слияние двух отсортированных прогонов в один
void merge(int arr[], int l, int m, int r) {
    int len1 = m - l + 1, len2 = r - m;
    int* left = (int*)malloc(len1 * sizeof(int));
    int* right = (int*)malloc(len2 * sizeof(int));
    
    // Копируем данные во временные массивы
    for (int x = 0; x < len1; x++) left[x] = arr[l + x];
    for (int x = 0; x < len2; x++) right[x] = arr[m + 1 + x];
    
    int i = 0, j = 0, k = l;
    
    // Сравниваем элементы и сливаем в исходный массив (в реальном коде здесь галопирование)
    while (i < len1 && j < len2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    
    // Дописываем оставшиеся элементы из левого массива
    while (i < len1) {
        arr[k] = left[i];
        k++; i++;
    }
    
    // Дописываем оставшиеся элементы из правого массива
    while (j < len2) {
        arr[k] = right[j];
        k++; j++;
    }
    
    free(left);
    free(right);
}

// Главная функция Timsort
void timSort(int arr[], int n) {
    // 1. Вычисляем оптимальную длину прогона
    int minRun = calcMinRun(n);
    
    // 2. Разбиваем массив на прогоны размером minRun и сортируем их вставками
    for (int i = 0; i < n; i += minRun) {
        int right = (i + minRun - 1 < n - 1) ? (i + minRun - 1) : (n - 1);
        insertionSort(arr, i, right);
    }
    
    // 3. Сливаем прогоны. Размер прогона увеличивается в 2 раза на каждом шаге
    for (int size = minRun; size < n; size = 2 * size) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = left + size - 1;
            int right = (left + 2 * size - 1 < n - 1) ? (left + 2 * size - 1) : (n - 1);
            
            // Если есть второй подмассив - сливаем их
            if (mid < right) {
                merge(arr, left, mid, right);
            }
        }
    }
}

# Полная реализация алгоритма Timsort на Python
MIN_MERGE = 32

def calc_min_run(n):
    """
    Вычисляет оптимальную длину прогона (minrun).
    Возвращает число от 32 до 64 такое, что n / minrun будет точной степенью двойки,
    или близко к ней.
    """
    r = 0
    # Пока массив длиннее 32, делим на 2
    while n >= MIN_MERGE:
        r |= n & 1  # Сохраняем "хвост" от нечетных делений
        n >>= 1     # Целочисленное деление на 2
    return n + r

def insertion_sort(arr, left, right):
    """
    Сортировка вставками. Оптимальна на очень коротких массивах (прогонах).
    """
    for i in range(left + 1, right + 1):
        temp = arr[i] # Запоминаем вставляемый элемент
        j = i - 1
        # Сдвигаем элементы вправо, пока они больше temp
        while j >= left and arr[j] > temp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = temp # Вставляем элемент

def merge(arr, l, m, r):
    """
    Функция слияния двух отсортированных прогонов.
    В оригинальном C-коде Python (listobject.c) здесь используется Галопирование (Galloping) -
    переход на экспоненциальный бинарный поиск, если один массив слишком долго "выигрывает".
    Здесь для простоты приведено стандартное линейное слияние, которое тоже работает за O(n).
    """
    len1, len2 = m - l + 1, r - m
    left_part = arr[l : m + 1]
    right_part = arr[m + 1 : r + 1]
    
    i, j, k = 0, 0, l
    
    # Сливаем два массива, перенося меньшие элементы в arr
    while i < len1 and j < len2:
        if left_part[i] <= right_part[j]:
            arr[k] = left_part[i]
            i += 1
        else:
            arr[k] = right_part[j]
            j += 1
        k += 1
        
    # Копируем остатки первого массива, если они есть
    while i < len1:
        arr[k] = left_part[i]
        k += 1
        i += 1
        
    # Копируем остатки второго массива, если они есть
    while j < len2:
        arr[k] = right_part[j]
        k += 1
        j += 1

def tim_sort(arr):
    """
    Главная функция Timsort.
    """
    n = len(arr)
    # 1. Считаем minrun
    min_run = calc_min_run(n)
    
    # 2. Разбиваем массив на блоки (прогоны) размером min_run.
    # В реальном коде алгоритм сам ищет уже отсортированные (естественные) прогоны,
    # и если они короче min_run - дополняет их с помощью сортировки вставками.
    for i in range(0, n, min_run):
        right = min(i + min_run - 1, n - 1)
        insertion_sort(arr, i, right)
        
    # 3. Начинаем сливать отсортированные прогоны.
    # В реальном алгоритме используется стек длин прогонов и сложные инварианты слияния.
    size = min_run
    while size < n:
        # Проходим по массиву шагами по 2*size
        for left in range(0, n, 2 * size):
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)
            
            # Сливаем два соседних прогона
            if mid < right:
                merge(arr, left, mid, right)
        
        # Увеличиваем размер сливаемых блоков в 2 раза
        size *= 2
    return arr

// Полная реализация алгоритма Timsort на JavaScript
const MIN_MERGE = 32;

// Функция для расчета размера минимального прогона
function calcMinRun(n) {
    let r = 0;
    // Делим на 2, пока n не станет меньше 32
    while (n >= MIN_MERGE) {
        r |= (n & 1); // Запоминаем остатки, чтобы не потерять элементы
        n >>= 1;      // Сдвигаем биты (делим на 2)
    }
    return n + r;
}

// Сортировка вставками для коротких массивов
function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
        let temp = arr[i]; // Берем элемент для вставки
        let j = i - 1;
        // Сдвигаем более крупные элементы вправо
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        // Записываем элемент
        arr[j + 1] = temp;
    }
}

// Классическое слияние (как в Merge Sort)
function merge(arr, left, mid, right) {
    const len1 = mid - left + 1;
    const len2 = right - mid;
    
    // Создаем временные массивы (в оригинальном V8 Timsort выделяется только один 
    // временный массив размером с меньшую из двух половин для экономии памяти)
    const leftArr = new Array(len1);
    const rightArr = new Array(len2);
    
    for (let x = 0; x < len1; x++) leftArr[x] = arr[left + x];
    for (let x = 0; x < len2; x++) rightArr[x] = arr[mid + 1 + x];
    
    let i = 0, j = 0, k = left;
    
    // Сливаем элементы обратно в оригинальный массив
    while (i < len1 && j < len2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }
    
    // Переносим остатки левого массива
    while (i < len1) {
        arr[k++] = leftArr[i++];
    }
    
    // Переносим остатки правого массива
    while (j < len2) {
        arr[k++] = rightArr[j++];
    }
}

// Главная функция Timsort
function timSort(arr) {
    const n = arr.length;
    // 1. Вычисляем minrun
    const minRun = calcMinRun(n);
    
    // 2. Нарезаем массив на прогоны размером minRun и сортируем их вставками
    for (let i = 0; i < n; i += minRun) {
        insertionSort(arr, i, Math.min(i + minRun - 1, n - 1));
    }
    
    // 3. Итеративно сливаем соседние прогоны. 
    // Изначально прогоны имеют размер minRun. Затем сливаются куски по 2*minRun, 4*minRun и т.д.
    for (let size = minRun; size < n; size = 2 * size) {
        for (let left = 0; left < n; left += 2 * size) {
            let mid = left + size - 1;
            let right = Math.min((left + 2 * size - 1), (n - 1));
            
            // Если правая половина существует, сливаем их
            if (mid < right) {
                merge(arr, left, mid, right);
            }
        }
    }
    return arr;
}