Cube Sort (Кубическая сортировка)

Краткое описание

Параллельный алгоритм сортировки, разработанный для многопроцессорных систем с кубической топологией (гиперкуб). Делит данные на блоки, распределяет по процессорам, локально сортирует каждый блок, затем объединяет с помощью параллельного слияния. В последовательной версии работает аналогично Merge Sort с оптимизациями для cache locality.

Когда использовать

• Параллельные вычисления — разработан специально для многопроцессорных систем
• Распределённые системы — эффективен при обработке больших данных на кластерах
• GPU вычисления — может быть адаптирован для CUDA/OpenCL
• Очень большие массивы — где параллелизм даёт значительное ускорение
• Системы с гиперкубической топологией — оптимизирован для такой архитектуры

Когда не стоит использовать:

• Однопроцессорные системы — последовательная версия не лучше обычного Merge Sort
• Маленькие массивы — накладные расходы на параллелизм не окупятся
• Простота важна — очень сложная реализация для production
• Ограниченная память — требует дополнительную память как Merge Sort
• Нестабильная нагрузка — может быть дисбаланс между процессорами

---

С объяснением логики работы

/**
 * Cube Sort (последовательная версия)
 * 
 * Это упрощённая версия для одного процессора.
 * Настоящий Cube Sort использует параллельную обработку на множестве процессоров.
 * 
 * Алгоритм:
 * 1. Делим массив на блоки (в параллельной версии — по числу процессоров)
 * 2. Сортируем каждый блок локально
 * 3. Выполняем последовательное слияние отсортированных блоков
 * 
 * В параллельной версии:
 * - Каждый процессор получает свой блок
 * - Все процессоры сортируют одновременно
 * - Слияние происходит параллельно по схеме гиперкуба
 */
 
/**
 * Слияние двух отсортированных массивов
 */
function merge(left, right) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;
 
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] <= right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
 
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
 
/**
 * Insertion Sort для малых блоков
 * В параллельной версии каждый процессор запускает это локально
 */
function insertionSort(arr, left = 0, right = arr.length - 1) {
    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;
    }
    return arr;
}
 
/**
 * Cube Sort (последовательная версия)
 * 
 * @param {Array} arr - массив для сортировки
 * @param {number} blockSize - размер блока (в параллельной версии = размер данных на процессор)
 */
function cubeSort(arr, blockSize = 32) {
    if (arr.length <= 1) return arr;
 
    // ШАГ 1: Делим массив на блоки
    // В параллельной версии каждый блок обрабатывается отдельным процессором
    const blocks = [];
    for (let i = 0; i < arr.length; i += blockSize) {
        const end = Math.min(i + blockSize, arr.length);
        blocks.push(arr.slice(i, end));
    }
 
    // ШАГ 2: Сортируем каждый блок локально
    // ПАРАЛЛЕЛЬНАЯ ФАЗА: все процессоры работают одновременно
    for (let i = 0; i < blocks.length; i++) {
        insertionSort(blocks[i], 0, blocks[i].length - 1);
    }
 
    // ШАГ 3: Слияние блоков
    // В параллельной версии используется схема гиперкуба
    // Процессоры объединяются попарно, затем четвёрками, и т.д.
    while (blocks.length > 1) {
        const mergedBlocks = [];
 
        for (let i = 0; i < blocks.length; i += 2) {
            if (i + 1 < blocks.length) {
                // Сливаем пары блоков
                mergedBlocks.push(merge(blocks[i], blocks[i + 1]));
            } else {
                // Если блоков нечётное число, последний переносим как есть
                mergedBlocks.push(blocks[i]);
            }
        }
 
        blocks.length = 0;
        blocks.push(...mergedBlocks);
    }
 
    // ШАГ 4: Копируем результат обратно
    const sorted = blocks[0];
    for (let i = 0; i < arr.length; i++) {
        arr[i] = sorted[i];
    }
 
    return arr;
}
 
// Пример использования
const numbers = [64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33, 77];
console.log("Исходный массив:", numbers);
cubeSort(numbers, 4);  // Блоки по 4 элемента
console.log("Отсортированный массив:", numbers);
 
/**
 * ВИЗУАЛИЗАЦИЯ РАБОТЫ на примере [8, 3, 5, 1, 9, 6, 7, 2] с blockSize=2:
 * 
 * ШАГ 1: Деление на блоки
 * [8, 3] | [5, 1] | [9, 6] | [7, 2]
 * 
 * ШАГ 2: Локальная сортировка (ПАРАЛЛЕЛЬНО)
 * Процессор 0: [8, 3] → [3, 8]
 * Процессор 1: [5, 1] → [1, 5]
 * Процессор 2: [9, 6] → [6, 9]
 * Процессор 3: [7, 2] → [2, 7]
 * 
 * Результат: [3, 8] | [1, 5] | [6, 9] | [2, 7]
 * 
 * ШАГ 3: Слияние (схема гиперкуба)
 * 
 * Раунд 1 (ПАРАЛЛЕЛЬНО):
 * Процессоры 0-1: merge([3, 8], [1, 5]) → [1, 3, 5, 8]
 * Процессоры 2-3: merge([6, 9], [2, 7]) → [2, 6, 7, 9]
 * 
 * Результат: [1, 3, 5, 8] | [2, 6, 7, 9]
 * 
 * Раунд 2:
 * Процессоры 0-3: merge([1, 3, 5, 8], [2, 6, 7, 9]) → [1, 2, 3, 5, 6, 7, 8, 9]
 * 
 * Финальный результат: [1, 2, 3, 5, 6, 7, 8, 9]
 */
 
/**
 * СХЕМА ГИПЕРКУБА для 8 процессоров:
 * 
 * Гиперкуб 3-го порядка (8 вершин = 2³):
 * 
 *     100 -------- 101
 *    /|           /|
 *   / |          / |
 * 110--------111  |
 *  |  000------|--001
 *  | /         | /
 *  |/          |/
 * 010---------011
 * 
 * Фазы слияния:
 * Фаза 1: пары по оси X (000↔001, 010↔011, 100↔101, 110↔111)
 * Фаза 2: пары по оси Y (000↔010, 001↔011, 100↔110, 101↔111)
 * Фаза 3: пары по оси Z (000↔100, 001↔101, 010↔110, 011↔111)
 * 
 * Каждая фаза выполняется ПАРАЛЛЕЛЬНО!
 */
 
/**
 * ПОЧЕМУ "CUBE" SORT:
 * 
 * Название происходит от топологии гиперкуба:
 * - Для n = 2^k процессоров используется k-мерный гиперкуб
 * - 2 процессора = линия (1D)
 * - 4 процессора = квадрат (2D)
 * - 8 процессоров = куб (3D)
 * - 16 процессоров = гиперкуб 4D
 * 
 * Преимущества гиперкуба:
 * - Логарифмический диаметр: O(log n) шагов для связи
 * - Хорошая масштабируемость
 * - Эффективная балансировка нагрузки
 */

---

С анализом сложностей

/**
 * Cube Sort с анализом сложности
 * 
 * ПОСЛЕДОВАТЕЛЬНАЯ ВЕРСИЯ:
 * - Временная сложность: O(n log n) — как Merge Sort
 * - Пространственная: O(n) — для временных блоков
 * 
 * ПАРАЛЛЕЛЬНАЯ ВЕРСИЯ (p процессоров):
 * - Временная сложность: O((n/p) log(n/p) + n log p)
 *   - Локальная сортировка: O((n/p) log(n/p))
 *   - Слияние log p раундов: O(n log p)
 * - При p = O(n / log n): O(log² n) — почти линейная!
 * 
 * ОСОБЕННОСТИ:
 * - Показанная последовательная реализация стабильна (insertionSort + merge с `<=`);
 *   нестабильность характерна для параллельных/гиперкубических схем слияния
 * - Не in-place
 * - Требует специальную архитектуру для полной эффективности
 */
 
function merge(left, right) {
    // ВРЕМЕННАЯ СЛОЖНОСТЬ: O(n + m)
    // где n = left.length, m = right.length
 
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;
 
    // Сравниваем и объединяем: O(n + m)
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] <= right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
 
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
 
function insertionSort(arr, left = 0, right = arr.length - 1) {
    // ВРЕМЕННАЯ СЛОЖНОСТЬ: O(k²) где k = размер блока
    // Для малых блоков (k ≤ 32): практически O(k) = O(1)
 
    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;
    }
    return arr;
}
 
/**
 * Cube Sort — последовательная версия
 * 
 * ДЕТАЛЬНЫЙ АНАЛИЗ:
 * 
 * Пусть:
 * - n = размер массива
 * - b = размер блока (blockSize)
 * - p = n/b = количество блоков (в параллельной версии = число процессоров)
 * 
 * ФАЗА 1: Создание блоков — O(n)
 * ФАЗА 2: Локальная сортировка
 *   - Последовательно: p блоков * O(b log b) = O((n/b) * b log b) = O(n log b)
 *   - ПАРАЛЛЕЛЬНО: O(b log b) — все процессоры работают одновременно!
 * 
 * ФАЗА 3: Слияние
 *   - Количество раундов: log₂(p) = log₂(n/b)
 *   - Каждый раунд: O(n)
 *   - Последовательно: O(n log(n/b))
 *   - ПАРАЛЛЕЛЬНО: каждый раунд тоже параллелится → O(n/p * log p)
 * 
 * ИТОГО:
 * Последовательная: O(n log b + n log(n/b)) = O(n log n)
 * Параллельная: O(b log b + n/p * log p)
 */
function cubeSort(arr, blockSize = 32) {
    if (arr.length <= 1) return arr;
 
    const n = arr.length;
    const p = Math.ceil(n / blockSize);  // Количество "процессоров"
 
    // ФАЗА 1: Деление на блоки
    // Время: O(n)
    // Память: O(n) для хранения блоков
    const blocks = [];
    for (let i = 0; i < n; i += blockSize) {
        const end = Math.min(i + blockSize, n);
        blocks.push(arr.slice(i, end));
    }
 
    // ФАЗА 2: Локальная сортировка
    // ПОСЛЕДОВАТЕЛЬНО: O(n log b)
    // ПАРАЛЛЕЛЬНО: O(b log b) — все p процессоров работают одновременно
    for (let i = 0; i < blocks.length; i++) {
        insertionSort(blocks[i], 0, blocks[i].length - 1);
    }
 
    // ФАЗА 3: Слияние (схема гиперкуба)
    // Количество раундов: log₂(p)
    // 
    // АНАЛИЗ РАУНДОВ:
    // Раунд 1: p/2 слияний блоков размера b
    //          Время одного слияния: O(2b)
    //          ПОСЛЕДОВАТЕЛЬНО: O(p/2 * 2b) = O(p*b) = O(n)
    //          ПАРАЛЛЕЛЬНО: O(2b)
    // 
    // Раунд 2: p/4 слияний блоков размера 2b
    //          ПОСЛЕДОВАТЕЛЬНО: O(n)
    //          ПАРАЛЛЕЛЬНО: O(4b)
    // 
    // ...
    // 
    // Раунд log p: 1 слияние блоков размера n/2
    //              ПОСЛЕДОВАТЕЛЬНО: O(n)
    //              ПАРАЛЛЕЛЬНО: O(n)
    // 
    // ИТОГО для фазы 3:
    // ПОСЛЕДОВАТЕЛЬНО: log₂(p) раундов * O(n) = O(n log p)
    // ПАРАЛЛЕЛЬНО: O(b) + O(2b) + O(4b) + ... + O(n) = O(n)
    //              (геометрическая прогрессия, доминирует последний член)
 
    let round = 1;
    while (blocks.length > 1) {
        const mergedBlocks = [];
 
        // В каждом раунде объединяем пары блоков
        for (let i = 0; i < blocks.length; i += 2) {
            if (i + 1 < blocks.length) {
                mergedBlocks.push(merge(blocks[i], blocks[i + 1]));
            } else {
                mergedBlocks.push(blocks[i]);
            }
        }
 
        blocks.length = 0;
        blocks.push(...mergedBlocks);
        round++;
    }
 
    // ФАЗА 4: Копирование — O(n)
    const sorted = blocks[0];
    for (let i = 0; i < arr.length; i++) {
        arr[i] = sorted[i];
    }
 
    return arr;
}
 
/**
 * ОПТИМАЛЬНЫЙ ВЫБОР blockSize:
 * 
 * Последовательная версия:
 * - blockSize должен помещаться в L1 cache (~32-64 элемента)
 * - Insertion Sort эффективен на малых данных
 * - Рекомендуется: 16-64
 * 
 * Параллельная версия:
 * - blockSize = n/p, где p = число процессоров
 * - Должен быть достаточно большим для окупаемости параллелизма
 * - Рекомендуется: n/p ≥ 1000
 */
 
/**
 * СРАВНЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ:
 * 
 * Для n = 1,000,000, p = 1000 процессоров:
 * 
 * ПОСЛЕДОВАТЕЛЬНЫЕ АЛГОРИТМЫ:
 * - Merge Sort: O(n log n) = O(20,000,000) операций
 * - Quick Sort: O(n log n) ≈ O(15,000,000) операций (лучшие константы)
 * - Cube Sort: O(n log n) = O(20,000,000) операций (аналогично Merge Sort)
 * 
 * ПАРАЛЛЕЛЬНЫЙ CUBE SORT:
 * - Локальная сортировка: O((n/p) log(n/p)) = O(1000 * 10) = O(10,000)
 * - Слияние: O(n) = O(1,000,000)
 * - ИТОГО: O(1,010,000) операций
 * - Ускорение: ~20x по сравнению с последовательным!
 * 
 * При оптимальном p = O(n / log n):
 * - Сложность: O(log² n)
 * - Для n = 1,000,000: O(400) операций
 * - Ускорение: ~50,000x (теоретически)
 */
 
console.log("Cube Sort (последовательная версия)");
console.log("Работает как оптимизированный Merge Sort");
console.log("Для реального ускорения нужна параллельная реализация");