1.7. ИСПОЛЬЗОВАНИЕ СЕЛЕКТОРОВ ПРЯМОГО ДОСТУПА

Одним из типичных случаев, когда требуется прямой доступ к частям выражения, являются алгоритмы, основанные на методе "разделяй и властвуй". Этот метод заключается в том, что исходная задача разбивается на подзадачи меньшего размера и решается для этих подзадач. Затем решение исходной задачи получается исходя из решений подзадач. Как правило, принцип "разделяй и властвуй" применяется совместно с принципом балансировки, гласящим, что исходную задачу следует разбивать на подзадачи примерно равного размера [АХУ 79].

В качестве классического примера рассмотрим задачу сортировки (т.е. упорядочения в порядке неубывания) множества целых чисел.

Одним из способов решения этой задачи является сортировка слиянием [АХУ 79], когда исходное множество чисел S разбивается на два непересекающихся множества S1 и S2 примерно равного размера. Затем S1 и S2 упорядочиваются независимо друг от друга. В результате получаются две упорядоченные последовательности чисел Q1 и Q2, которые соединяются (сливаются) в одну упорядоченную последовательность Q, которая и является решением исходной задачи.

Теперь определим функцию MSort, которая получает на входе последовательность целых чисел, разбивает ее на две примерно равные части, сортирует их (обратившись к себе рекурсивно), а затем сливает получившиеся последовательности, обратившись к функции Merge.