Сортировка слиянием (Merge Sort) — это алгоритм сортировки, основанный на принципе "разделяй и властвуй". Он рекурсивно делит массив на две половины, сортирует каждую половину, а затем объединяет (сливает) отсортированные половины в один отсортированный массив.
Основные шаги:
- Разделение: Если массив содержит более одного элемента, он делится на два подмассива примерно равного размера.
- Рекурсивная сортировка: Сортировка слиянием рекурсивно вызывается для каждой из двух подмассивов.
- Слияние: Отсортированные подмассивы объединяются (сливаются) в один отсортированный массив.
python
Сложность алгоритма:
| Операция | Временная сложность | Пространственная сложность |
|---|
| Наихудший случай | O(n log n) | O(n) |
| Средний случай | O(n log n) | O(n) |
| Наилучший случай | O(n log n) | O(n) |
Преимущества:
- Гарантированная временная сложность O(n log n) во всех случаях (наилучшем, среднем, наихудшем).
- Стабильная сортировка (сохраняет относительный порядок равных элементов).
Недостатки:
- Требует дополнительной памяти O(n) для слияния подмассивов.