Что такое сортировка слиянием

Сортировка слиянием (Merge Sort) — это алгоритм сортировки, работающий по принципу «разделяй и властвуй». Он рекурсивно разбивает массив на две части, сортирует каждую из них, а затем объединяет (сливает) отсортированные части в один массив.

Основные шаги:

1. Разделение: массив делится пополам, пока не останутся подмассивы из одного элемента (которые уже отсортированы).
2. Слияние: два отсортированных подмассива объединяются в один, с поэлементным сравнением.

Пример на Python:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        merge_sort(left)
        merge_sort(right)
        
        i = j = k = 0
        
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

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

• Стабильная сортировка (сохраняет порядок равных элементов).
• Сложность всегда O(n log n), даже в худшем случае.

Недостатки:

• Требует дополнительной памяти O(n) для хранения подмассивов.