#Вопросы_с_собеседования
Реализуйте алгоритм сортировки слиянием (Merge Sort) на Python. Напишите код и объясните, как работает этот алгоритм. Расскажите о его сложности и возможных оптимизациях.

Объяснение:
Алгоритм сортировки слиянием (Merge Sort) использует стратегию «разделяй и властвуй». Он состоит из двух основных шагов:

Разделение (Divide): Массив разделяется на две равные (при четном числе элементов) или почти равные (при нечетном) части. Этот процесс рекурсивно выполняется для каждой из подпоследовательностей.
Слияние (Merge): Отсортированные подпоследовательности сливаются обратно в один отсортированный массив.

Сложность:
Временная сложность: O(n log n) в худшем, лучшем и среднем случаях.
Пространственная сложность: O(n).

Оптимизации:
— При реализации можно использовать вставочную сортировку для маленьких подмассивов, так как у нее меньшая константа в асимптотике.
— Если массив уже отсортирован, можно добавить проверку и пропустить шаг сортировки.
— Вместо копирования подмассивов при каждом рекурсивном вызове можно использовать вспомогательный массив для слияния, что уменьшит использование памяти.