Введение
Разделяй и властвуй — это алгоритмическая техника, в которой мы решаем задачу, разбивая её на меньшие подзадачи, решая эти подзадачи рекурсивно, а затем объединяя их ответы.
Типичный алгоритм «разделяй и властвуй» следует трём основным шагам:
- Разделить — разбить задачу на меньшие подзадачи;
- Завоевать — решить подзадачи рекурсивно;
- Объединить — объединить ответы подзадач в окончательный ответ.
Эта идея встречается во многих важных алгоритмах.
Сортировка слиянием
Условие
Дан массив