Pythoner
Фотография
✈️Сортировка слиянием - это один из наиболее эффективных алгоритмов сортировки, который используется в программировании. Он основан на принципе "разделяй и властвуй", что позволяет ему достичь быстрого времени выполнения.
➡️Принцип работы
Сортировка слиянием работает путем разделения неотсортированного массива на две половины, сортировки каждой из них отдельно, а затем слияния двух отсортированных массивов обратно в один. Это делается рекурсивно, что означает, что процесс разделения и слияния продолжается, пока весь массив не будет отсортирован.
➡️Реализация в Python
В Python сортировка слиянием может быть реализована с помощью стандартной библиотеки. Функция merge_sort принимает список в качестве аргумента и возвращает отсортированный список. Она делит список на две половины, рекурсивно вызывает себя для каждой половины, а затем объединяет два отсортированных списка в один.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
merged = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
merged += left[left_index:]
merged += right[right_index:]
return merged
➡️Преимущества и недостатки
Сортировка слиянием имеет несколько ключевых преимуществ. Во-первых, она эффективна, с временем выполнения O(n log n). Во-вторых, она стабильна, что означает, что она сохраняет исходный порядок равных элементов. Однако у нее есть и недостатки. Она требует дополнительное пространство для хранения промежуточных результатов, что может быть проблемой для больших данных.
🐍Pythoner
31 · 2.4K ·