Что такое алгоритм «разделяй и властвуй»?

Хорошо, что задал — это один из самых универсальных приёмов в алгоритмах.

«Разделяй и властвуй» (divide and conquer) — это стратегия из трёх шагов:

1. Разделить задачу на несколько подзадач поменьше (обычно того же типа).
2. Решить каждую подзадачу рекурсивно (а совсем маленькие — напрямую, это база рекурсии).
3. Объединить ответы подзадач в ответ для исходной.

Это больше чем просто рекурсия. Рекурсия — инструмент; «разделяй и властвуй» — это конкретный паттерн, где задача дробится на независимые части, а потом результаты собираются вместе.

Классический пример — merge sort:

def merge_sort(arr):
    if len(arr) <= 1:           # база: 0 или 1 элемент уже отсортирован
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # делим и решаем левую половину
    right = merge_sort(arr[mid:])  # и правую

    return merge(left, right)      # объединяем

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

print(merge_sort([5, 2, 8, 1, 9, 3]))  # [1, 2, 3, 5, 8, 9]

Откуда берётся O(n log n)? Рассуждаем простыми словами:

• На каждом уровне рекурсии мы делим массив пополам → всего получается log n уровней (сколько раз n можно делить на 2 до единицы).
• На каждом уровне суммарно мы сливаем все n элементов → O(n) работы на уровень.
• Перемножаем: log n уровней × n работы = O(n log n).

То же рассуждение формализуют через рекуррентное соотношение: T(n) = 2·T(n/2) + O(n). «2 подзадачи размера n/2 плюс O(n) на слияние» — решение как раз даёт O(n log n).

Другие примеры:

• Бинарный поиск: делим диапазон пополам, спускаемся в одну половину → O(log n).
• Quick sort: делим по опорному элементу, сортируем части → в среднем O(n log n).

Итог: увидел «разбить → решить рекурсивно → объединить» — это он.