The general idea is to solve a problem by dividing it into subproblems - each an instance of
the original problem but on inputs of smaller size - in such a way that the solution of the
original problem can be assembled from the solutions to the subproblems. The principle
divide and conquer
is usually applied together with the principle of "balancing"
requiring that the original problem should be divided into subproblems of roughly equal size
[AHU1974].
A classic application of the principle divide and conquer
is the problem of sorting
(i.e. arranging in ascending order).
One of the sorting methods is the merge sort [AHU1974]. The idea is to divide the
original set S into two disjoint sets S1 and
S2 of roughly equal size, sort S1 and S2 to
produce two ordered sequences Q1 and Q2, and then merge
Q1 and Q2 into one ordered sequence Q,
thereby obtaining the solution to the original problem.
Now let us define the function MSort, which takes an integer sequence as
argument, divides it into two parts of approximately equal size, and calls itself recursively
in order to sort both parts. Then the sequences thus obtained are merged by the function Merge
to produce the final result.
$func MSort eS = eS;
$func Merge (eX)(eY) = eZ;
MSort eS =
<Length eS> :: sLen,
{
<Le (sLen) (1)>
= eS;
= <Div sLen 2> :: sK,
<Left 0 sK eS> :: eS1,
<Middle sK 0 eS> :: eS2,
<Merge ( <MSort eS1> )( <MSort eS2> )>;
};
Now we have to define the function Merge, which takes two ordered integer sequences as
arguments and merges them into one ordered sequence.
Merge (eX)(eY) =
{
eX :
= eY;
eY :
= eX;
(eX)(eY) : (sA eXRest)(sB eYRest)
= {
<Le (sA)(sB)>
= sA <Merge (eXRest)(eY)>;
= sB <Merge (eX)(eYRest)>;
};
};