Сортировка слиянием: разделяй и властвуй

🎯 Зачем это нужно?

Представь: у тебя 1 миллион фото в телефоне, и нужно отсортировать их по дате 📱. Обычная сортировка “пузырьком” будет работать часами! А merge sort справится за секунды.

💼 Где используется: - Google/Yandex поиск: сортировка миллиардов результатов поиска - Spotify/Apple Music: ранжирование треков по популярности
- YouTube: сортировка комментариев по времени - Банки: обработка миллионов транзакций в реальном времени

📚 История вопроса

В 1945 году Джон фон Нейман придумал merge sort для первого компьютера EDVAC. Интересно: идея появилась не от математики, а от наблюдения за тем, как библиотекари объединяют уже отсортированные картотеки! 📚

Сегодня это основа сортировки в Java (Arrays.sort), Python (sorted), и многих базах данных.

💡 Интуиция

Представь сортировку колоды карт:

🃏 Наивный способ: перебираем все карты, ищем минимальную, откладываем… 52 раза. Долго!

🧠 Умный способ (merge sort): 1. Разделяем колоду пополам → 2 стопки по 26 карт 2. Каждую стопку снова пополам → 4 стопки по 13 карт 3. Продолжаем до стопок по 1 карте (они уже “отсортированы”!) 4. Начинаем объединять: 2 стопки по 1 → 1 стопка из 2 (отсортированная) 5. Продолжаем объединять отсортированные стопки

[МЕДИА: image_01] Описание: Визуализация разделения массива на половины и последующего слияния Промпт: “educational diagram showing merge sort divide and conquer process, array being split into halves recursively, then merged back together, step-by-step visualization, modern clean style, suitable for computer science students”

📐 Формальное определение

Merge Sort - алгоритм сортировки, основанный на принципе “разделяй и властвуй”:

1. Divide: Разделить массив пополам
2. Conquer: Рекурсивно отсортировать обе половины
   
3. Combine: Слить два отсортированных массива в один

Временная сложность: O(n log n) - всегда! Не зависит от исходного порядка Пространственная сложность: O(n) - нужен дополнительный массив Стабильность: Да - элементы с одинаковыми ключами сохраняют относительный порядок

🔍 Примеры с разбором

Пример 1: Сортировка [38, 27, 43, 3, 9, 82, 10]

Фаза разделения: [38, 27, 43, 3, 9, 82, 10] ↓ [38, 27, 43, 3] | [9, 82, 10] ↓ ↓ [38, 27] [43, 3] | [9, 82] [10] ↓ ↓ ↓ ↓ [38] [27] [43] [3] [9] [82] [10] code Code Фаза слияния: [27, 38] [3, 43] | [9, 82] [10] ↓ ↓ [3, 27, 38, 43] | [9, 10, 82] ↓ [3, 9, 10, 27, 38, 43, 82] code Code [МЕДИА: image_02] Описание: Пошаговая визуализация слияния двух отсортированных массивов Промпт: “step-by-step merge process visualization, two sorted arrays being combined into one, pointers showing current positions, educational animation style, clear color coding”

Пример 2: Алгоритм слияния

Как объединить [1, 5, 8] и [2, 3, 7]?

```python def merge(left, right): result = [] i = j = 0

# Сравниваем элементы и добавляем меньший
while i < len(left) and j < len(right):
    if left[i] <= right[j]:
        result.append(left[i])
        i += 1
    else:
        result.append(right[j])
        j += 1

# Добавляем оставшиеся элементы
result.extend(left[i:])
result.extend(right[j:])
return result

Пошагово: i=0, j=0: 1 ≤ 2 → добавляем 1, result=[1] i=1, j=0: 5 > 2 → добавляем 2, result=[1,2] i=1, j=1: 5 > 3 → добавляем 3, result=[1,2,3] i=1, j=2: 5 ≤ 7 → добавляем 5, result=[1,2,3,5] Остались [8] и [7] → result=[1,2,3,5,7,8] 🎮 Практика Базовый уровень 🟢 Задание 1: Слей два отсортированных массива [1, 4, 6] и [2, 3, 5, 8] вручную