💾 Merge Sort — сортировка слиянием по принципу «разделяй и властвуй»: массив делится рекурсивно, пока не останутся части из одного элемента, затем они сливаются в упорядоченный массив.

def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
return merge(left, right)

def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result

arr = [9, 3, 41, 67, 2, 19, 0, 84]
print(merge_sort(arr)) # [0, 2, 3, 9, 19, 41, 67, 84]

#MergeSort #Python #Алгоритмы
pythonpedia