IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Optimal Disk

Merge Patterns

Maurice Schlumberger

Jean Vuillemin

Rapport de Recherche n° 4

Janvier 1973
# OPTIMAL DISK MERGE PATTERNS

M. Schlumberger* - J. Vuillemin

(présenté par J.M. Cadiou)

## Abstract :

Our purpose is to study the optimal way to merge n initially sorted
runs, stored on a disk like device, into a unique sorted file. This problem is
equivalent to finding a tree with n leaves which minimizes a certain cost func-
tion. (See Knuth [1]).

We shall study some properties of those optimal trees, in the hope of
finding efficient ways for constructing them.

In particular, if all the initial runs have the same length, an algo-
rithm for constructing the best merge pattern is described ; its running time is
proportional to n² and it requires space proportional to n.

A special case is also analyzed in which the problem is solved in time
and space proportional to n, which provides some insight into the asymptotic beha-
vior optimal merge trees.

## 1. Introduction

The problem is to merge n initially sorted runs $a_1, a_2, ..., a_n$
into a single disk file by a succession of merge operations. A merge-pattern is
best described by a merge-tree having $a_1, a_2, ..., a_n$ for leaves.

For example, the trees corresponding to the various ways of merging
three runs $a_1, a_2, a_3$ are :

<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /></figure>

Here $a_1, a_2, a_3$ means that we first merge $a_1$ and $a_2$ into a run of size $a_1 + a_2$ which is then merged with $a_3$ in order to obtain a sorted file of size $a_1 + a_2 + a_3$. Note that, for the simplicity of our notation, we identify the name of a run with its length, or weight as we shall call it.

The weight $w(T)$ of a tree $T$ is the sum of the weights of the leaves of $T$. To each merge-tree $T$, we associate two quantities $E(T)$ and $D(T)$ defined as follows:

- The external path length $E(T)$ is the sum over all leaves of $T$ of the weight of each leaf multiplied by the distance between this leaf and the root of $T$.

- The degree path length $D(T)$ is the sum over all leaves of $T$ of the weight of each leaf multiplied by the sum of the degrees of the nodes on the path connecting this leaf to the root of $T$.

For example, if $T$ is

then

<figure><img src="image_6.png" /></figure>

$$E(T) = 2a_1 + 2a_2 + a_3$$
$$\text{and } D(T) = 4a_1 + 4a_2 + 2a_3$$

The relevance of those two quantities to disk-merging is shown in Knuth [1]: the time spent in transfers between disk and main storage is proportional to $E(T)$ and the number of disk accesses during the merge process proportional to $D(T)$.

To each merge-tree $T$ we associate a cost function $C(T)$ by the formula

$$C(T) = \alpha D(T) + \beta E(T) \quad (1)$$

where $\alpha$ and $\beta$ are some coefficients depending on the characteristics of the disk and the computer used.

An optimal merge-tree $T$ for the runs $a_1, \dots, a_n$ minimizes $C(T)$ over all trees having the same leaves.

Note that the special case $\alpha = 0$, i.e when disk-access is given for free, can be cast away at once: optimal trees then have all their leaves directly connected to the root. We shall assume from now on that $\alpha \neq 0$.
## 2. Properties of optimal trees

Any merge process can be split arbitrarily into two stages: first we merge some initial runs together, and the resulting file is then merged with the others initial runs. If the corresponding pattern is to be optimal, each of these two stages must itself be optimal.

In order to give a precise content to this remark, we define the contraction $T/T'$ of a merge-tree $T$ by one of its subtrees $T'$ to be a merge-tree obtained by replacing in $T$ the whole subtree $T'$ by a leaf having $w(T')$ for weight.

For example, if $T =$

<figure><img src="image_7.png" /></figure>

and $T' =$

<figure><img src="image_8.png" /></figure>

Then $T/T' =$

<figure><img src="image_9.png" /></figure>

For any tree $T$ and subtree $T'$ of $T$, it follows easily from our definitions that

$$C(T) = C(T') + C(T/T') \quad (2)$$

The easiest way to make use of this formula is the following

**Theorem 1** In an optimal merge-tree $T$, 
(i) any subtree is optimal and 
(ii) any contraction $T/T'$ of $T$ by one of its subtrees $T'$ is also optimal.

*Proof:* The proof is straightforward by contradiction. ■

<figure><img src="image_10.png" /></figure>

Ensuring that any two successive stages of a merge process are optimal does not imply that the whole merge is itself optimal, and the converse of theorem 1 is not true.

This theorem constitutes our basic tool throughout this paper. Although it already gives some hints on how to construct optimal merge trees, the algorithms one can derive from Theorem 1 are not very efficient. We shall therefore study some more properties of optimal trees before describing algorithms for constructing them.

In a first step, we prove that the order of merges in optimal trees need not be arbitrarily large :
**Theorem 2** There exists an optimal merge tree T of cost $C(T) = \alpha D(T) + \beta E(T)$ in which the degree of any node is at most $d_{max}$ where

$$d_{max} = \left\lceil \min_{k \ge 1} \left\{ k + \left(1 + \frac{1}{k}\right) \left(1 + \frac{\beta}{\alpha}\right) \right\} \right\rceil \quad (3)$$

**Proof :**

Suppose that an optimal tree T has a node i of degree d with $d > d_{max}$. By theorem 1, the subtree T' having i for root must be optimal. By theorem 1 again, the contraction $K = a_1 a_2 \dots a_d$ of T', where $a_1, a_2, \dots, a_d$ are the weights of the subtrees of T', must also be optimal. We shall transform K into an equivalent (or better) tree K' of nodes $a_1, a_2, \dots, a_d$ having a degree equal to $d_{max}$. The tree K' can in turn be used for constructing an optimal merge-tree T' which resembles T except that the number of nodes having degree greater than $d_{max}$ has diminished by one. By by iterating this procedure, one can obtain an optimal merge-tree satisfying the hypothesis of Theorem 2.

For any integer $2 < k + 1 < d$, let

$K' = \overbrace{a_1 a_2 \dots a_{k+1}}^{a_{k+2} \dots a_d}$. By definition of the cost function,

$C(K) - C(K') = \alpha k (\sum_{1 \le i \le d} a_i) - (\alpha(k+1) + \beta) (\sum_{1 \le i \le k+1} a_i)$. If we now choose $a_1 \le a_2 \le \dots \le a_{k+1}$, we have $(\sum_{1 \le i \le k+1} a_i) \le \frac{k+1}{d} (\sum_{1 \le i \le d} a_i)$ hence

$C(K) - C(K') \ge A k(d-k- (1+\frac{1}{k})(1+\frac{\beta}{\alpha}) - 1)$ where $A = \frac{\alpha}{d} (\sum_{1 \le i \le d} a_i)$. This inequality being valid for any k, we can strengthen it to $C(K) - C(K') \ge A k_0(d - d_{max} - 1)$, where $k_0$ minimizes equation (3).

Since $d > d_{max}$ by hypothesis, $C(K) - C(K')$ must be non-negative and K' is also optimal. ■

Together with theorem 1, Theorem 2 reduces the amount of search for optimal trees among all possible merge trees.
It does not seem enough however to result in an efficient algorithm for constructing optimal trees in the general case, i.e when the initial runs have arbitrary lengths, and the authors know of no non-exponential algorithm in this case.

However, the situation becomes easier when all initial runs have the same length, and there is a good practical reason for being interested in this special case : in general, all initial runs are likely to have been constructed by the same process (say some sorting in core memory) and will indeed have the same length.

From now on, we shall turn our attention to this special case.

### 3. Initial runs having equal length

#### 3.1. General case

- A lower bound on the degrees of the nodes in an optimal merge tree

If we take the weight of each leaf equal to one, the weight $w(T)$ of a merge-tree $T$ becomes the number of its leaves (a tree reduced to its root has weight one). We shall denote by $C(\alpha, \beta, n)$ the cost of an optimal tree with $n$ leaves. It is also convenient to define $d(T)$ as the degree of the root of the merge-tree $T$.

As a first step, let us prove that the "small" optimal merge-trees are "flat", that is

**Lemma 1:**

If $2 \le n \le d_{max}$ where $d_{max}$ is defined by (3), a flat tree $F$ with $n$ leaves of depth one, ($i$-e $d(F) = w(F) = n$) is optimal.

Let $n_o$ be the least natural number for which the flat tree $F$ with $d(F) = w(F) = n_o$ is not optimal. We must prove that $n_o \ge d_{max} + 1$

Suppose that $S = \bigcup_{i=1}^k s_i$ with $w(S) = n_o$ is optimal. Since any of the subtrees $s_i$ is optimal by theorem 1, it is equivalent to a flat tree ($n_o$ minimal). We can therefore compute

$$C(S) = \alpha n_o + \beta n_o + \sum_{1 \le i \le k} g(w(s_i))$$

$$\text{where } g(x) = \text{if } x = 1 \text{ then } 0 \text{ else } \alpha x^2 + \beta x$$
is the cost of a flat tree.
Without loss of generality, we assume that $w(s_1) \ge 2$. If we now consider the trees $T =$ and $F$ flat with $w(T) = w(F) = n_o$, we shall prove that $S$ optimal implies $C(T) \le C(F)$. The conclusion of Lemma 1 then follows from the calculation done in the proof of Theorem 2 which tells us that $C(T) \le C(F)$ for any $T$ implies $n_o \ge d_{max} + 1$.

<figure><img src="image_11.png" /></figure>

In order to prove now that $S$ optimal implies $C(T) \le C(F)$, we consider the tree $U =$ of weight $w(U) = n_o$.

<figure><img src="image_12.png" /></figure>

A simple calculation yields $C(T) - C(F) = C(S) - C(U)$. Arguing by contradiction, $C(F) < C(T)$ would therefore imply $C(U) < C(S)$, and $S$ would not be optimal. $\blacksquare$

This lemma shows that, when initial runs have equal length, we cannot improve on the upper-bound given in Theorem 2.

We shall now derive the following lower bound on the degrees of the nodes in optimal trees :

**Theorem 3**

Let $k = k(\alpha, \beta)$ be a natural number such that
$$ \underline{k(k-1) \le 1 + \beta/\alpha < k(k+1)} \qquad (4) $$

There exists an optimal tree $T$ which satisfies
$$ \underline{d(T) \ge \text{if } w(T) \le d_{max} \text{ then } w(T) \text{ else } d_{min}} $$

where $d_{min} = \max(3, k+1)$.

**Proof :**

First of all, we notice that a number $k$ satisfying (4) will minimize the expression (3) defining $d_{max}$. The numbers $d_{min}$ and $d_{max}$ are therefore related by $d_{min} (d_{min} - 1) \le d_{max} + 1 \le d_{min} (d_{min} + 1)$, unless $d_{min} = 3$.

The proof is then by induction on the number $n$ of initial runs.

In lemma 1, we showed that theorem 3 is true for $n \le d_{max}$, and whenever $\beta/\alpha \le 1$, we can easily check it up to $n_o = d_{min} (d_{min} - 1) = 6$.

Assuming that the theorem is true for all $n < n_o$ with $n_o > d_{min} (d_{min} - 1)$, consider an optimal tree $T_o$ such that

$$ w(T_o) = n_o \text{ and } d(T_o) = d \text{ with } d < d_{min} $$

(If there none, the proof is finished).
We must show that there exists an optimal tree $T_2$ such that $w(T_2) = w(T_0)$ while $d(T_2) \ge d_{\min}$. For this purpose, it is sufficient to show that as long as $d(T_0) < d_{\min}$ there exists an optimal tree $T_1$ such that $w(T_1) = w(T_0)$ and $d(T_1) = d(T_0) + 1$.

Before constructing $T_1$, we need to prove the following

**Properties of $T_0$:**

It will be convenient to call **principal subtree** of a tree T any subtree whose root is an immediate successor of the root of T (level 1 subtrees).

Let us partition the principal subtrees $A_1, A_2, \dots, A_d$ of $T_0$ into the three classes :

$$ \text{class 1} = \{A_i \mid w(A_i) = 1\} $$

$$ \text{class 2} = \{A_i \mid 1 < w(A_i) \le d\} $$

$$ \text{class 3} = \{A_i \mid d < w(A_i)\} $$

We shall prove by contradiction that class 2 must be empty. Let S be some subtree in class 2 and L be the principal subtree of $T_0$ of largest weight. We consider the transformation

<figure><img src="image_13.png" /></figure>

where S and L have been changed to S' and L', the other $A_i$'s being untouched. We obtain S' and L' by transfering the principal subtree s of L having minimal weight from L to s in a way such that

$$ w(L') = w(L) - w(S) \quad \text{and} \quad d(L') = d(L) - 1 \quad \text{while} $$

$$ w(S') = w(S) + w(S) \quad \text{and} \quad d(S') = d(S) + 1. $$

We can compute

$$ C(T_0) - C(T'_0) = \alpha\{w(L) - w(S) + w(S)(d(L) - d(S) - 2)\}. $$ 
Because of our choice of L, $w(L) \ge \frac{n_o - w(S)}{d-1}$ and, since

$w(S) \le d$ and $n_o \ge d_{\min} (d_{\min} - 1) \ge d_{\min} d$, it follows that $w(L) \ge d_{\min} \frac{d}{d-1} > d_{\min}$. We therefore know by the induction hypothesis that L can be chosen such that $d(L) \ge d_{\min}$ and $C(T) - C(T') \ge \alpha\{w(L) - w(S) - w(S)\}$. Because of our choice of s, $w(S) \le \frac{w(L)}{d(L)} \le \frac{w(L)}{d_{\min}}$ and therefore

$$ C(T_0) - C(T'_0) > \alpha\{d_{\min} (1 - \frac{1}{d_{\min}}) - (d_{\min} - 1)\} = 0. $$ This contra-

dicts the assumption that $T_0$ is optimal and class 2 must indeed be empty.
### Construction of $T_1$

Going back to the main argument, we know that we can partition the principal subtrees of $T_0$ into $\{A_i | w(A_i) = 1\}$ and $\{A_i | w(A_i) > d\}$. Without loss of generality, we can assume that

$$w(A_1) \ge w(A_2) \ge \dots \ge w(A_m) > d \text{ and}$$

$$w(A_{m+1}) = w(A_{m+2}) = \dots = w(A_d) = 1 \text{ for some } 1 \le m \le d.$$

Let $s_1, s_2, \dots, s_m$ be some principal subtrees respectively of $A_1, A_2, \dots, A_m$. We construct $T_1$ as follows:

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

A simple calculation yields

$$C(T_0) - C(T_1) \ge \alpha \left\{ \sum_{1 \le i \le m} w(s_i) (d(A_i) - m - 1) + (m-d) \right\}.$$

Since by the induction hypothesis, $d(A_i) \ge d + 1$ we have

$$C(T_0) - C(T_1) \ge \alpha(d - m) \left( \sum_{1 \le i \le m} w(s_i) - 1 \right) \ge \alpha(d - m) \ge 0.$$

Since $T_0$ is optimal, $T_1$ must also be optimal. ■

### An algorithm for constructing optimal merge-tree

Using our knowledge about optimal trees, let us describe an algorithm for computing the cost $C(\alpha, \beta, n)$. (This algorithm can be modified in a simple way so as to construct optimal merge trees).

Following Knuth [1], we realize that the definition

$$C(\alpha, \beta, n) = \min_{d, \min \le d \le d} \left\{ \min_{\max} \left\{ \alpha n + \beta n + \sum_{i=1}^{d} C(\alpha, \beta, a_i) \right\} \right\} \\ = n$$

is suitable for dynamic programming techniques, and, if we define

$$A(d, n) = \min_{a_1 + \dots + a_d = n} \left\{ \sum_{i=1}^{d} C(\alpha, \beta, a_i) \right\} \text{ when } 2 \le d \le n \text{ and}$$

$A(1, n) = \binom{n}{1}$, the function A can be computed recursively as
Algorithm 1 :

$$
A(d,n) = \underset{n \le d}{\text{if}} \underset{\max}{\text{then}} A(1, \lfloor \frac{n}{d} \rfloor) + A(d-1, n-\lfloor \frac{n}{d} \rfloor) \\
\qquad \underset{1 \le i \le \frac{n}{d}}{\text{else}} \min \{A(1,i) + A(d-1, n-i)\} \\
\qquad \text{when } 2 \le d \le n \text{ and}
$$

$$
A(1,n) = \underset{n=1}{\text{if}} \underset{\max}{\text{then}} \underset{0}{\text{else}} \\
\qquad \underset{n \le d}{\text{if}} \underset{\max}{\text{then}} \beta n + \alpha n^2 \\
\qquad \qquad \underset{\min}{\text{else}} \min \{\beta n + \alpha dn + A(d,n)\} \\
\qquad \qquad \qquad d \le d \le \max
$$

The iterative version of this procedure where the A(d,n) are kept in
an array of size O(n) runs in time O(n²).
Although algorithm 1 is already reasonably efficient, it is suspected
that a better knowledge of large optimal trees would provide a much better algo-
rithm. We shall illustrate this fact for special case $β/α ≤ 1/2$.

### 3.2. Special case $β/α ≤ 1/2$

- A closer look at optimal trees when $β/α ≤ 1/2$

Whenever $β/α ≤ 1$, we know by theorems 2 and 3 that the degree of the root of optimal trees is either three or four. In fact, when $β = 0$ we know that this degree is exactly three. Starting there, some experimental evidence suggests that, for $β/α ≤ 1/2$, the degrees of the roots of optimal trees for small values of $n$ oscillate somewhat strangely between three and four. It then stabilizes to three from a certain value $n_0$ on ($n_0$ depends upon $β/α$) and furthermore, large optimal trees seem fairly well balanced. Those facts will be proved in Lemma 2 and Theorem 4, which give us enough information about optimal trees when $β/α ≤ 1/2$ to construct them efficiently in algorithm 2.

**Lemma 2**

> If $β/α ≤ 1/2$, for any natural number $n > n_0$, (where $n_0$ is some small ($n_0 ≤ 51$) number), there exists an optimal tree $T$ such that $w(T) = n$ and $d(T) = 3$.

**Proof :**

Let us admit for the moment that lemma 2 has been checked for all values between $n_0$ and some large $n_1$ to be determined later.

Assuming the lemma to be true for all $m < n$, with $n > n_1$, we must show the existence of a ternary optimal tree $T$ of weight $n$. By Theorem 3, we know that $d(T_0)$ is either three or four.
Let us therefore assume that $d(T_0) = 4$. (If $d(T_0) = 3$, the proof is finished). Let $S_1, S_2, S_3$ and $S_4$ be the principal subtrees of $T_0$, named in a way such that $d(S_1) \le d(S_2) \le d(S_3) \le d(S_4)$. The construction of $T_1$ will depend on the value of $d(S_1)$.

$$ - \underline{\text{Case } d(S_1) \le 2} $$

By Theorem 3, $d(S_1) \le 2$ implies $w(S_1) \le 2$. If we choose $n_1 > 14$, then $S_4$ must have a principal subtree $s$ of weight $w(s)$ greater than 2. By exchanging $S_1$ and $s$, we would then obtain a tree of cost lesser than $T_0$, a contradiction.

$$ - \underline{\text{Case } d(S_1) = 4} $$

Because of the induction hypothesis, $d(S_1) = \dots = d(S_4) = 4$ implies $w(S_1) \le n_0, \dots, w(S_4) \le n_0$. We can discard this case by choosing $n_1 \ge 4 n_0$.

$$ - \underline{\text{Case } d(S_1) = 3} $$

If $d(S_2) = 4$ we construct $T_1$ as

<figure><img src="image_16.png" /></figure>

gives

<figure><img src="image_17.png" /></figure>

where the $s_{ij}$ are the principal subtrees of $S_i$.

We can compute $C(T_0) - C(T_1) = \alpha w(S_1) - \beta(w(S_2) + w(S_4))$. Since $w(S_2) \le n_0$, $w(S_3) \le n_0$ and $w(S_4) \le n_0$ by the induction hypothesis, it follows that $w(S_1) \ge n_1 - 3 n_0$ and therefore $C(T_0) - C(T_1) \ge \alpha(n_1 - \frac{9}{2} n_0)$. It is then sufficient to choose $n_1 \ge \frac{9}{2} n_0$ in order to get the optimality of $T_1$.
If $d(S_2) = 3$ and $d(S_3) = 4$ we construct $T_1$ as

<figure><img src="image_18.png" /></figure>

gives

<figure><img src="image_19.png" /></figure>

where we choose $w(s_{22}) + w(s_{23}) \ge \frac{2}{3}w(S_2) \ge \frac{1}{3}(n_1 - 2n_0)$.

As before, we get $C(T_0) - C(T_1) \ge \frac{\alpha}{3}(n_1 - 5n_0)$ which entails the choice $n_1 \ge 5n_0$.

If $d(S_3) = 3$ and $d(S_4) = 4$ the construction of $T_1$ is

<figure><img src="image_20.png" /></figure>

gives

<figure><img src="image_21.png" /></figure>
with $w(s_{33}) \ge \frac{1}{3} w(s_3) \ge \frac{1}{9} (n_1 - n_0)$.

In this case, $C(T_0) - C(T_1) \ge 0$ whenever $n_1 \ge \frac{11}{2} n_0$.

Finally, if $d(S_4) = 3$, we use

<figure><img src="image_22.png" /></figure>

gives

<figure><img src="image_23.png" /></figure>

and $C(T_1) = C(T_0)$ with no condition on $n_1$.

To summarize, we know that lemma 2 would be proved if only we could check it for all values between $n_0$ and $n_1 = \lceil \frac{11}{2} n_0 \rceil$.

If we run a computer program for $\beta/\alpha = \frac{1}{2}$, we realize that $n_0 = 51$ and that lemma 2 is indeed satisfied for all values between 51 and 281. (When $\beta/\alpha = 1/4$, the value of $n_0$ is 4 and we only need checking up to 22).

Of course, we cannot run a computer program for each value of $\beta/\alpha$! However, using the same technique as in all our previous proofs, it is not too hard to prove that, if the tree $T_0$ is optimal for $\beta_0/\alpha_0$ there exists an optimal tree $T_1$ optimal for $\beta_1/\alpha_1 < \beta_0/\alpha_0$ such that $w(T_1) = w(T_0)$ and $d(T_1) \le d(T_0)$.

This in turn implies that, for any $\beta/\alpha \le 1/2$, lemma 2 is indeed true for values between 51 and 281 and, a fortiori, for values between $n_0$ and $\lceil \frac{11}{2} n_0 \rceil$ for some $n_0 < 51$. ■

Knowing the degrees of the nodes in large optimal tree will allow us to determine the relative weights of their principal subtrees.

After behaving rather badly for values of $n$ less than $n_0$, large optimal trees then grow in a rather nice pattern, namely :
**Theorem 4**

If $\beta/\alpha \le 1/2$, for any $n$ there exists an optimal tree of weight $n$ such that, for any of its principal subtrees $S_i$ and $S_j$, $|w(S_i) - w(S_j)| \le M$, where $M$ is a constant number.

**Proof :**

Starting at an arbitrary optimal tree $T_0$ satisfying lemma 2, we shall successively transform it into equivalent optimal trees $T_1, T_2, \dots$ until theorem 4 is satisfied.

First of all, let $T_1$ be obtained from $T_0$ by contracting all the subtrees of $T_0$ of weight less than $n_0$, where $n_0$ is defined as in lemma 2.

If we define the depth of a node (or leaf) as the distance between this node (leaf) and the root of the tree, we shall first prove that, in $T_1$, the difference between the depth of any two leaves is at most one.

Well, let $m$ be a leaf at depth $t$; if there is a leaf of depth greater than $t+1$, there must exists a subtree $S = \bigcup_{a_1, a_2, a_3}^{m}$ where $a_1, a_2$ and $a_3$ are leaves of $T_1$, at depth $t'+t+1$. If this were the case, we could transform $T_1$ into $T_1'$ by replacing $S$ by $a_1$ and $m$ by $\bigcup_{a_2, a_3}^m$. This would give $c(T_1) - c(T_1') \ge (3\alpha+\beta)(w(S) - w(m))$. Since all subtrees of $T_1$ of weight less than $n_0$ have been contracted, $w(S) > n_0 \ge w(m)$ and therefore $T_1$ would not be optimal.

We now know that all the leaves of $T_1$ have depth $t$ or $t+1$ for some $t$.

We construct $T_2$ by contracting all subtrees of $T_1$ having a root of depth $t$. The tree $T_2$ now has a very nice shape : it is ternary and all of its 3$^t$ leaves have the same depth $t$ ; by construction, each leaf $m$ has a weight $w(m)$ such that $1 \le w(m) \le 3n_0$.

Without changing the cost, we can "move" the leaves as we please. In particular, we can partition the leaves in three classes such that the difference between the sum of the weights of the leaves in any two classes does not exceed

$$ \Sigma_i = M. $$
This is done by numbering the leaves in order of increasing weight, $1 \le i \le 3n_0$
and assigning the $i$-th leaf to the $(i \bmod 3)$-th class.
The leaves in each of these three classes are then assigned respectively ot the three principal subtree of T<sub>2</sub>, in order to obtain a tree T<sub>3</sub>.

We then replace each leaf of T<sub>3</sub> by the subtree of which it is a contraction, and end up with an optimal tree T<sub>4</sub> satisfying the conditions of Theorem 4. ■

- An efficient algorithm for constructing optimal trees when $\beta/\alpha \le 1/2$

Using lemma 2 and Theorem 4 we can describe a modification to algorithm 1 which, when coded as an iterative routine, runs in time and space proportional to n. The cost C(1,n) of an optimal tree having n leaves can be computed by

Algorithm 2

$$C(1,n) = \underset{\text{else}}{\text{if }} n \le n_0 \quad \underset{\text{then}}{A(1,n)}$$

$$C(d,n) = \underset{n/d - M \le i \le n/d}{\underset{\text{else}}{\text{if }} n \le n_0} \quad A(d,n)$$

where A(d,n) is to be computed by algorithm 1 while $n_0$ and M are defined as in lemma 2 and Theorem 4.

4 - Conclusion

Although some progress has been made into the study of optimal merge patterns, the answer to many interesting questions is still unknown.

For example, can one find an efficient (non-exponential) algorithm for constructing optimal merge trees when initial runs have arbitrary lengths (or prove that there is none) ?

This may provide some insight into another open question, namely the asymptotic behaviour of the cost function for optimal merge trees over equal length runs, when $\beta/\alpha \ge 1/2$. Related to this is the question of existence of a linear time and space algorithm for constructing optimal trees over equal length runs, when $\beta/\alpha$ is arbitrary.

As a possible approach to this last question, one may try to prove that there are optimal trees in which the difference in depth between any two leaves does not exceed one, as suggested by empirical data.
Acknowledgments

We are grateful to Donald Knuth for letting us use some of his earlier
unpublished work on the subject, and to Jean Marie Cadiou for his help in pre-
paring the manuscript.

Reference

Knuth [1] : Donald E. Knuth "The art of computer programming" vol 3 section 5-4-9. Addison Wesley.