Сортировка слиянием (Merge Sort)

Проект реализует алгоритм сортировки слиянием на Python для сортировки матриц по сумме их диагональных элементов.

Описание

Сортировка слиянием — это эффективный алгоритм сортировки, использующий подход "разделяй и властвуй". Алгоритм делит массив пополам, рекурсивно сортирует обе половины, а затем объединяет их в отсортированный массив.

Как работает алгоритм

1. Разделение: Массив делится пополам на две части
2. Рекурсия: Каждая половина рекурсивно сортируется
3. Слияние: Отсортированные половины объединяются в один отсортированный массив

Особенности реализации

В данном проекте алгоритм используется для сортировки матриц по сумме их главной диагонали:

• Класс Matrix создает матрицу и вычисляет сумму диагональных элементов
• Функция merge_sort реализует рекурсивную сортировку слиянием
• Функция merge_two_lists объединяет два отсортированных списка матриц

Временная сложность

• Лучший случай: O(n log n)
• Средний случай: O(n log n)
• Худший случай: O(n log n)

Алгоритм всегда имеет сложность O(n log n), что делает его предсказуемым и надежным.

Пространственная сложность

O(n) — требуется дополнительная память для хранения временных массивов при слиянии

Преимущества

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

Недостатки

• Требует дополнительной памяти O(n)
• Не работает "на месте" (in-place)
• Может быть медленнее, чем быстрая сортировка для небольших массивов

Использование

Программа принимает на вход:

1. Количество матриц k
2. Для каждой матрицы:
   • Размер матрицы
   • Элементы матрицы (построчно)

Программа выводит индексы матриц, отсортированных по сумме их диагональных элементов.

Пример ввода:

3
3
1 2 3
4 5 6
7 8 9
2
10 20
30 40
2
1 1
1 1

Пример вывода:

0
1
2
0 1 2

Требования

• Python 3.x

Структура кода

• Matrix — класс для представления матрицы с вычислением суммы диагонали
• merge_sort(arr) — рекурсивная функция сортировки слиянием
• merge_two_lists(a, b) — функция объединения двух отсортированных списков
• main() — основная функция программы

Автор

Проект создан в рамках изучения алгоритмов сортировки ст. Бобковым Владиславом Дмитриевичем