Метка: Сортировка слиянием

Сортировка слиянием — это эффективный алгоритм сортировки, работающий по принципу «разделяй и властвуй». Он обладает стабильностью и гарантированной сложностью O(n log n).

📌 Алгоритм сортировки слиянием

• Разделение массива на две половины
• Рекурсивная сортировка каждой половины
• Слияние отсортированных половин

💻 Реализация на PHP

<?php
function mergeSort(array $arr): array {
    if (count($arr) <= 1) {
        return $arr;
    }
    
    $middle = (int)(count($arr) / 2);
    $left = mergeSort(array_slice($arr, 0, $middle));
    $right = mergeSort(array_slice($arr, $middle));
    
    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $result = [];
    $i = $j = 0;
    
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $result[] = $left[$i++];
        } else {
            $result[] = $right[$j++];
        }
    }
    
    return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}

// Пример использования
$array = [38, 27, 43, 3, 9, 82, 10];
$sorted = mergeSort($array);
print_r($sorted);
?>

🌐 Реализация на JavaScript

1. Классическая версия

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    
    const middle = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, middle));
    const right = mergeSort(arr.slice(middle));
    
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    
    return result.concat(left.slice(i)).concat(right.slice(j));
}

// Пример использования
const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(array));

2. Версия с визуализацией шагов

function mergeSortWithSteps(arr, level = 0) {
    console.log(`${'  '.repeat(level)}Сортируем:`, arr);
    
    if (arr.length <= 1) {
        console.log(`${'  '.repeat(level)}Базовый случай:`, arr);
        return arr;
    }
    
    const middle = Math.floor(arr.length / 2);
    const left = mergeSortWithSteps(arr.slice(0, middle), level + 1);
    const right = mergeSortWithSteps(arr.slice(middle), level + 1);
    
    const merged = merge(left, right);
    console.log(`${'  '.repeat(level)}Сливаем ${left} и ${right} →`, merged);
    
    return merged;
}

const nums = [5, 2, 4, 7, 1];
console.log("Исходный массив:", nums);
console.log("Результат:", mergeSortWithSteps(nums));

⚡ Сравнение с другими алгоритмами

Характеристика	Merge Sort	Quick Sort	Bubble Sort
Сложность (средняя)	O(n log n)	O(n log n)	O(n²)
Сложность (худшая)	O(n log n)	O(n²)	O(n²)
Память	O(n)	O(log n)	O(1)
Стабильность	Да	Нет	Да

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

• Плюсы Merge Sort:
  • Гарантированная сложность O(n log n)
  • Стабильность (сохраняет порядок равных элементов)
  • Хорош для связных списков и внешней сортировки
• Минусы:
  • Требует дополнительной памяти O(n)
  • Медленнее Quick Sort на небольших массивах

Оптимальное применение: большие массивы (от 10k элементов), где важна стабильность.

Другие виды сортировок

• Quick Sort — быстрая сортировка
• Bubble Sort — сортировка пузырьком