Алгоритмы

Merge Sort: Разделяй и властвуй

Цели урока

  • Понять парадигму Divide and Conquer
  • Реализовать Merge Sort
  • Доказать O(n log n) через Master Theorem
  • Знать применение в External Sort

Предварительные знания

  • O(n²) сортировки
  • Рекурсия
  • O(n²) сортировки
  • Рекурсия

В 1945 году Джон фон Нейман изобрёл Merge Sort для первых компьютеров. 80 лет спустя этот же алгоритм сортирует петабайты данных в Google и Amazon. Почему он выжил?

  • External Sort в базах данных (PostgreSQL, MySQL)
  • MapReduce shuffle phase
  • Unix `sort` для больших файлов
  • Timsort (Python, Java) - гибрид с Insertion Sort

История Merge Sort

Джон фон Нейман описал Merge Sort в 1945 году - это один из первых алгоритмов, разработанных специально для компьютеров. Изобретение совпало с созданием EDVAC, одного из первых электронных компьютеров.

Divide and Conquer

**Divide and Conquer** - парадигма решения задач через разбиение на подзадачи:

  1. **Divide** - разбить задачу на меньшие подзадачи
  2. **Conquer** - рекурсивно решить подзадачи
  3. **Combine** - объединить решения в итоговый ответ

Сколько уровней рекурсии в Merge Sort для массива из 8 элементов?

Ключевая операция: Merge

**Merge** - слияние двух отсортированных массивов в один отсортированный. Это O(n) операция!

**Стабильность:** используем `<=` вместо `<` при сравнении. Это сохраняет порядок равных элементов.

Merge двух массивов по n/2 элементов работает за:

Полный алгоритм

**In-place версия** (без создания новых массивов) сложнее, но экономит память:

База рекурсии в Merge Sort - это:

Анализ сложности

**Time Complexity:** O(n log n) - всегда! Best, Average, Worst - одинаковы.

**Space Complexity:** O(n) - нужен временный массив для merge.

ХарактеристикаMerge Sort
Best caseO(n log n)
Average caseO(n log n)
Worst caseO(n log n)
SpaceO(n)
СтабильностьДа
In-placeНет (стандартная версия)

**Master Theorem:** T(n) = 2T(n/2) + O(n) → T(n) = O(n log n). Это универсальная формула для анализа Divide & Conquer.

Merge Sort на уже отсортированном массиве работает за:

External Sort: когда данные не влезают в RAM

**Главное применение Merge Sort** - внешняя сортировка, когда данные слишком большие для RAM.

**K-way merge** использует min-heap размера k для эффективного выбора минимума. Сложность: O(n log k).

**Примеры использования External Sort:**

  • Базы данных - сортировка таблиц, которые не влезают в память
  • MapReduce - shuffle phase использует external sort
  • Unix `sort` команда - автоматически переключается на внешнюю сортировку
  • Big Data - обработка логов, датасетов терабайтного размера

**Почему именно Merge Sort?** Потому что merge последователен - читаем и пишем большими блоками, минимизируя seek на диске. Quick Sort требует random access.

Для внешней сортировки Merge Sort лучше Quick Sort потому что:

Merge Sort

  • Divide: делим массив пополам
  • Conquer: рекурсивно сортируем половины
  • Combine: сливаем отсортированные половины за O(n)
  • Всегда O(n log n), стабильный
  • O(n) дополнительной памяти
  • Идеален для External Sort (диск)

Связанные алгоритмы

Merge Sort - не единственный O(n log n). Quick Sort быстрее на практике, Heap Sort экономит память.

  • Quick Sort — Быстрее на практике, но O(n²) worst case
  • Heap Sort — O(1) память, но не стабильный
  • Divide & Conquer — Парадигма алгоритмов

Связанные уроки

  • alg-06-quick-sort — Quick Sort - альтернатива с лучшей cache locality, но без гарантии O(n log n) worst case и без стабильности
  • alg-07-heap-sort — Heap Sort тоже O(n log n) гарантировано, но in-place за счёт cache misses - обратный trade-off
  • alg-19-divide-conquer — Merge Sort - каноничный пример Divide & Conquer: рекурсия описывается Master Theorem T(n)=2T(n/2)+O(n)
  • prog-09-recursion — Без понимания рекурсии и стека вызовов нельзя объяснить, почему база - массив из 1 элемента
  • alg-08-counting-sort — Non-comparison сортировки - следующий шаг: понять, почему Merge Sort не может быть быстрее O(n log n)
  • ds-02-linked-lists
Merge Sort: Разделяй и властвуй

0

1

Войти