# Design of optimal merge on direct access devices

Laurent Hyafil, Francis Prusker, Jean Vuillemin

► To cite this version:

Laurent Hyafil, Francis Prusker, Jean Vuillemin. Design of optimal merge on direct access devices. [Research Report] IRIA-RR-039, IRIA. 1973, pp.15. hal-04715960

HAL Id: hal-04715960

https://inria.hal.science/hal-04715960v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

laboratoire de recherche
en informatique
et automatique

Design of optimal merge
on direct access devices

L. Hyafil, F. Prusker,
J. Vuillemin

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

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n° 39
novembre 1973
DESIGN OF OPTIMAL MERGE ON DIRECT ACCESS DEVICES

L. Hyafil, F. Prusker, J. Vuillemin

**Abstract :**

Our goal in this paper is to provide a model and its mathematical analysis for optimal merging on direct access devices such as disks, drums, magnetic-cards, ... thus allowing one to make rational design decisions. We present various algorithms and heuristics for efficiently computing optimal merge patterns, when the runs generated in the initial sorting phase have reasonably equal lengths.

The analysis which we provide for optimal merges gives ways to choose the best merge-pattern in a given configuration, evaluate the effect of having longer initial runs, and decide between a faster disk or a larger core memory.

**Résumé :**

Dans cet article nous présentons l'analyse mathématique d'un modèle de fusion optimale sur des supports externes à accès direct comme des disques, des tambours ou des cartes magnétiques. Nous présentons divers algorithmes et heuristiques pour le calcul efficace de schémas de fusion optimaux lorsque les monotonies créées dans la phase initiale du tri sont de tailles approximativement égales.

L'analyse que nous donnons des fusions optimales permet de choisir le meilleur schéma de fusion pour une configuration donnée, d'évaluer l'influence de la longueur des monotonies initiales, de choisir entre un disque plus rapide et une mémoire centrale plus grande.
# 1. INTRODUCTION.

It can be estimated that about 20 % of all computing time ([$1$]) is spent on sorting per se, about half of it being spent on sorting with external direct access devices. The usual approach to sorting on such devices is to split the process in two stages. In the initial stage, one generates, through an internal sort, a sequence of initial sorted runs which are stored on the external device. In the subsequent stage, those runs are repeatedly merged together, until a unique sorted file results. The *merge pattern* is a tree describing in which order should the initial runs be merged. For example, if the initial runs are $r_1, r_2$ and $r_3$, the possible merge patterns are

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

for example means that we first merge $r_2$ and $r_3$ together in order to obtain a sorted run of size $size(r_2) + size(r_3)$ which is then merged with $r_1$ in order to complete the sort.

The object of this paper is to study *optimal merge patterns* leading to the fastest merge among all possible merges. If the initial runs created by the internal sort have very unequal lengths, we have good reasons to believe that the problem of computing those optimal merge-patterns is a very hard one. On the other hand, if those initial runs have approximately equal lengths, and this will be the case with all known methods of internal sorting when the keys in the input file are randomly distributed, we shall describe efficient methods for computing optimal merge-patterns. We then analyse the time taken by this optimal merge as a function of various parameters, such as the size of core memory, the speed of the external device or the length of the initial runs, thus allowing to optimize the choice of those parameters.
## 2. MODELS FOR THE MERGE.

At a typical step in the merge process, we have to combine the sorted runs $r_1, \dots, r_d$ (stored on the external device) of respective sizes $n_1, \dots, n_d$ into a unique sorted sequence $r_o$ of size $n_o = n_1 + \dots + n_d$. Here $d$ is the merge order. To each run $r_i$ with $0 \le i \le d$ we associate a buffer of size $b_i$ in core memory. The choice of the $b_i$'s will be discussed later; however, if $M$ is the size of the available core memory, it is clear that $\sum_{0 \le i \le d} b_i = M$.

Each buffer $b_i$ except $b_o$ is filled in, (from the external device), with records from run $r_i$. We then start an internal merging of $b_1, \dots, b_d$ into $b_o$ until either $b_o$ becomes full or one of the $b_i$'s empty. The appropriate buffer is then emptied (resp. filled) and the process continues until $n_o$ is fully created. The time taken by this merge can be split into three factors: access time, transfer time and CPU time. We shall neglect here the CPU time, although this is no real restriction since the methods we develop here are powerful enough to cope with this case, at the price of slightly more complex equations. The transfer time is clearly equal to $2 \mathcal{C}_T n_o$ where $\mathcal{C}_T$ is a unitary transfer time depending on the device's hardware.

Since there are $\sum_{0 \le i \le d} \frac{n_i}{b_i}$ accesses per buffer, the total access time is $\mathcal{C}_A \cdot \sum_{0 \le i \le d} \frac{n_i}{b_i}$ where $\mathcal{C}_A$ is the access-time of the device; the merge time $\mathcal{M}$ is therefore:

$$ \mathcal{M} = (2 \mathcal{C}_T n_o + \mathcal{C}_A \sum_{0 \le i \le d} \frac{n_i}{b_i}) \quad (1) $$

In most computer systems, this model is not quite accurate. For example, with disks, the access time should be divided into the sum of the arm-movement-time ("seek time") plus the rotational latency. Also, either the core memory or the secondary storage area may be divided into pages, which affects the merge time. However, on all variations of the basic model which we studied, our techniques are applicable and the results are roughly similar. The model leading to formula (1),
which we call *Model 1* from now on, was studied by Ferguson [2], and he discovered that the optimal way to allocate the buffers was to choose

$$b_i = M \frac{\sqrt{n_i}}{\sum_{0 \le i \le d} \sqrt{n_i}} \quad (2)$$

This is not necessarily the case with other models. For example, if the secondary storage is paged, and the size of the core-memory is a moderately large multiple of the page size, then all buffer-sizes should be chosen equal to the page size. As mentioned earlier, this does not affect the methods or the results and we shall confine our attention to Model 1.

Using (1) and (2), the cost of a merge is

$$M = (2 \sum_{T} n_{o} + \sum_{A} n_{i} \cdot (\sum_{0 \le i \le d} \sqrt{n_{i}})^{2}) \quad (3)$$

Let $C_i(n)$ be the cost of, i.e. the time taken by, an optimal merge of n equal-size (normalized to a unit length) sorted initial runs. It was proved by Knuth [3] that $C_i(n)$ is given by

$$C_i(1) = 0 \\ C_i(n) = \min_{2 \le d \le n} \left\{ \min_{\sum n_i = n} \left[ 2 \sum_{T} n + \sum_{A} \frac{n}{M} \left( \sqrt{n} + \sum \sqrt{n_i} \right)^2 + \sum_{1 \le i \le d} C_i(n_i) \right] \right\} \quad (4)$$

Intuitively, if we start with equal length runs, there should be no reason why one ever needs to merge runs of very different size. For practical purposes, it might therefore be worthwhile to allocate equal size buffers to the input files in the merge process, thus optimizing only on the size of the output buffer. We shall give later a deeper mathematical reason to be interested in this particular merging scheme. With this particular buffer allocation, the optimal choice of $b_o$ is
$b_o = \frac{M\sqrt{d}}{d+\sqrt{d}}$ and, for $1 \le i \le d$, $b_i = \frac{M}{d+\sqrt{d}}$. This leads to the following formula for computing $C_2(n)$:

$$ \begin{cases} C_2(1) = 0 \\ C_2(n) = \min_{2 \le d \le n} \left[ \varphi(d) \cdot n + \min_{\sum n_i = n \atop 1 \le i \le d} \left( \sum C_2(n_i) \right) \right] \end{cases} \quad (5) $$

with $\varphi(d) = \alpha(1+\sqrt{d})^2 + \beta$, $\alpha = \frac{\mathcal{C}_A}{M}$ and $\beta = \frac{2\mathcal{C}_T}{M}$. This other model will be refered to as Model 2.

### 3. PROPERTIES OF OPTIMAL MERGE PATTERNS.

In order to study some properties of optimal merge patterns in Model 2, we first show that $C_2(n) \ge k n \log n$ for some k. If $n = 1$, the inequality is true. Assuming it to be true for all $m < n$, we prove it for n : by (5), we know that $C_2(n) = \varphi(d)n + \sum_{1 \le i \le d} C_2(n_i)$ for some $d, n_1, \dots, n_d$ with $\sum_{1 \le i \le d} n_i = n$. By induction, $\sum_{1 \le i \le d} C_2(n_i) \ge \sum_{1 \le i \le d} k n_i \log n_i$.

The function $x \log x$ is convex for $x > 0$ and therefore $\sum_{1 \le i \le d} n_i \log n_i \ge d(\frac{n}{d}) \log(\frac{n}{d}) = n \log n - n \log d$. So far, we have thus established that

$$ C_2(n) \ge k n \log n + n (\varphi(d) - k \log d) \quad (6) $$

Elementary calculus tells us that the function $\frac{\varphi(x)}{\log x}$ has exactly one minimum for $x > 1$ and therefore there is one (possibly two) natural number $d_{lim}$ such that

$$ \frac{\varphi(d)}{\log d} \ge \frac{\varphi(d_{lim})}{\log d_{lim}} \quad (7) $$

for all natural numbers d. It follows that we can choose
$$k = \frac{\varphi(d_{\text{lim}})}{\log d_{\text{lim}}} = \min_{d \ge 2} \frac{\varphi(d)}{\log d} \quad (8)$$

so as to obtain $C_2(n) \ge k n \log n$.

In order to see how "tight" this lower bound is, we study a particular class of merge-patterns, namely the _complete d-ary trees_ as defined in Knuth [4]. Roughly, a complete d-ary tree has as many nodes with degree d, and is as "balanced" as possible. One can exactly compute the cost $\mathcal{H}_1(n)$ of a merge of n equal initial runs using a complete d-ary tree for merge pattern:

If $n = d^t + (d-1)r + s$ with $d^t < n \le d^{t+1}$, $0 \le r < d^t$ and $1 \le s \le d-1$, this cost is

$$\mathcal{H}_1(n) = \varphi(d)(nt + rd) + (s + 1)\varphi(s + 1) \quad (9)$$

If we choose $d = d_{\text{lim}}$, it is easy to see that $\mathcal{H}_1(n) \le k n \log n + K n$ where k is given by (8) and K is large enough. We have therefore proved that

$$k n \log n \le C_2(n) \le k n \log n + K n \quad (10)$$

and furthermore, it is easily seen from (9) that, whenever $n = (d_{\text{lim}})^q$ for some $q \ge 1$, the cost $\mathcal{H}_1(n)$ with $d = d_{\text{lim}}$ is exactly equal to $C_2(n)$. The lower bound in (10) is therefore tight and reached in finitely often.

Going back to the preceding section on models, we see that the proof of (10) does not carry through in a straightforward manner to the function $C_1(n)$ defined in Model 1. Using some slightly more involved mathematics, it is possible to establish that $C_1(n)$ also satisfies (10) -see [5]-. Furthermore, experimental evidence (to the extent that one has enough computer time for computing $C_1$) suggests that $C_1(n) \approx C_2(n)$ to within a few percent.
We now use inequalities (10) and (6) for proving that large orders of merge can always be avoided in optimal merge patterns. This fact greatly contributes to improving the algorithms and heuristics presented in the next section. Let us first notice that, for $x > d_{lim}$, the function $\varphi(x) - k \log x$ is increasing and unbounded. Therefore there exists a smallest natural number $d_{max}$ such that

$$ \varphi(d_{max}) - k \log d_{max} \geq K \quad (11) $$

with k and K defined by (8) and (10).

It follows that in any optimal merge-pattern, the merge order d of any node is such that

$$ d \leq d_{max} \quad (12) $$

otherwise, there would be a contradiction between inequalities (10) and (6). This result was also obtained in [6], with a slightly different model, by completely different combinatorial techniques.

## 4. EFFICIENT WAYS FOR COMPUTING OPTIMAL MERGE PATTERNS.

We first describe algorithms for computing optimal merge patterns, or rather for computing the cost of optimal merges since it is easy, as shown by Knuth [4], to construct information describing the merge pattern while computing its cost. In Model 1, finding an efficient way for computing the function $C_1(n)$ satisfying (4) is still an open problem. The best algorithm suggested in [4] takes an exponential time in terms of n. By proving in [5] that inequality (12), i.e, $d \leq d_{max}$ is also valid in Model 1, the authors have reduced this timing to $O(n^{d_{max}})$. This is still rather unpractical, since typical values of $d_{max}$ are of the order of 20 or more.

On the other hand, if we restrict buffer-optimization to that of the output buffer, i.e., compute $C_2(n)$ satisfying (5), dynamic programming techniques provide efficient ways for computing $C_2(n)$ (see [4] and [6]).
For this purpose, let

$$A(d,n) = \min_{\substack{\sum n_i = n \\ 1 \le i \le d}} \left[ \sum_{1 \le i \le d} C_2(n_i) \right] \quad (13)$$

so that $A(1,n) = C_2(n)$.

The function A can be computed recursively by :

Algorithm 1 :

(i) $A(1,1) := 0$;

(ii) **For** $2 \le d \le \min(d_{max},n)$ **do**
$A(d,n) := \min_{1 \le i \le n \atop d}$ $[A(1,i) + A(d-1,n-i)]$;

(iii) $A(1,n) := \min_{2 \le d \le d_{max}} [n\phi(d) + A(d,n)]$;

The iterative version of this procedure where the $A(d,n)$ are kept in an array of size $n \cdot d_{max}$ runs in time $O(n^2)$.

A much faster procedure, running in time $O(\log n)$ is described by the authors in [7]. Unfortunately, this method has a high overhead cost which makes it less efficient than Algorithm 1 for most practical values of n.

Despite the fact that there exists rather efficient algorithms for computing optimal merge patterns, one should also be aware of the existence of very good heuristics for finding near-optimal solutions.

The first idea suggested by the analysis of section 3 is to use complete d-ary trees with $d = d_{lim}$ as merge patterns. Whenever the number n of initial runs is a power of $d_{lim}$, i.e., $n = (d_{lim})^q$ for $q \ge 1$, or close to such a number, we know that this particular merge pattern will be optimal. However, the experimental results given in Tab 1 show that, for some other values of n, this method can lead to merges which are 20 % slower than the optimal one.
This suggests that it should be worthwhile spending a little more
time choosing a merge pattern. Another straightforward idea is to use
Algorithm 1 as if all sub-patterns at the same level had the same
size, i.e. $|n_i - n_j| \le 1$ in (5). This can be expressed by the
recursive definition of function $\mathcal{H}_2$:

Heuristic 2 :

$$
(i) \mathcal{H}_2(1) := 0;
$$

$$
(ii) \mathcal{H}_2(n) := \min_{2 \le d \le d_{\max}} \left[ n\phi(d) + \sum_{0 \le i < d} \mathcal{H}_2\left(L\left(\frac{n+i}{d}\right)\right) \right]; \quad (14)
$$

An iterative implementation of Heuristic 2 runs in time and
space O(n). Using the fact that we need not compute ℌ₂(m) for all
m < n in order to compute ℌ₂(n), it is possible to lower this to O[(log n)²],
where p is the number of primes smaller than d_max.

This heuristic leads to much better merge patterns that the
previous one. However, in the course of a merge according to such a
pattern, the merge-order may vary, while with complete d-ary trees,
this merge order is always d<sub>lim</sub>, exep t possibly for one merge.

Also, both heuristics $\mathcal{H}_1$ and $\mathcal{H}_2$ may lead to merge patterns
where all leaves are **not** all at the same level. If one has two disks
for example, the merge will send all records alternatively on each
disk, and merge-patterns where leaves are not at the same level, hence
not necessarily on the same disk to start with, are quite useless.

We shall describe yet another heuristic, Heuristic 3, which avoids
all those defects. It is an elaboration of the method of Black [8] .
The idea is to choose the best possible merge pattern where only two
values, d and d - 1 are possible merge orders, and choose the best
possible such pattern.

The merge is done in p passes. During the first pass, we perform
q merges with merge order d, and r merges with merge order (d - 1).
Then, for (p - s) passes, the merge order is set to (d - 1). Finally,
the merge order for the (s - 1) remaining passes is d.
The integers d, q, r and s are related to the number p of
passes as follows : the merge-order d is the only integer solution
to the inequality (d - 1)^p < n ≤ d^p ; quantity s is then determined
by d^s-1 (d - 1)^p-s+1 < n ≤ d^s (d - 1) ^p-s and, q and r are given by
q = n - d^s-1 (d - 1)^p-s + 1 and r = d^s (d-1) ^p-s -n. A graphical repre-
sentation of such a merge pattern is given in Fig 1.

<figure><img src="image_4.png" /><figcaption>Fig 1.</figcaption></figure>

The cost of a merge using such a pattern is

$$
\begin{align*}
\mathcal{H}(n,p) ={}& qd(s\varphi(d) + (p-s)\varphi(d-1)) \\
& + r(d-1)((s-1)\varphi(d) + (p-s+1)\varphi(d-1)).
\end{align*}
$$

Heuristic 3 then chooses the pattern which minimizes this cost over all
depths p :

$$
\mathcal{H}_3(n) = \min_{1 \le p \le \log_2 n} [\mathcal{H}(n,p)] \quad (15).
$$

An easy analysis also shows that Heuristic 3 takes O(log n)
steps and a constant size memory.

It is now time to compare the efficiency of the merge patterns
computed by those algorithms and heuristics. The theoretical results
can be summarized by $C_1(n) \le C_2(n) \le \mathcal{H}_2(n) \le \mathcal{H}_3(n)$ and
$C_2(n) \le \mathcal{H}_1(n)$. Also, if $n = (d_{1im})^q$ (and around such values), all
methods lead to the same optimal merge pattern. An experimental comparison
between the various methods for significant values of n is given in Table 1.
For each n this table shows $C_2$ and $h_1$, $h_2$, $h_3$ differences in percent between
$C_2$ and $\mathcal{H}_1$, $\mathcal{H}_2$, $\mathcal{H}_3$ respectively.
<table><caption>Table 1</caption><thead><tr><th></th><th>α = 0.0086</th><th>β = 1,6667</th><th>γ/α = 193.79</th><th>d<sub>lim</sub> = 58</th></tr><tr><th>n</th><th>5</th><th>10</th><th>20</th><th>30</th><th>50</th><th>100</th><th>200</th><th>500</th></tr></thead><tbody><tr><th>C<sub>2</sub></th><td>8.8</td><td>18.2</td><td>38.5</td><td>60.8</td><td>111.3</td><td>270.7</td><td>727.7</td><td>1948.9</td></tr><tr><th>h<sub>1</sub></th><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>19.4</td><td>8.1</td><td>12.0</td></tr><tr><th>h<sub>2</sub></th><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td></tr><tr><th>h<sub>3</sub></th><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.1</td><td>0.0</td><td>0.0</td></tr></tbody></table>

<table><thead><tr><th></th><th>α = 0.086</th><th>β = 1,6667</th><th>γ/α = 19.38</th><th>d<sub>lim</sub> = 12</th></tr><tr><th>n</th><th>5</th><th>10</th><th>20</th><th>30</th><th>50</th><th>100</th><th>200</th><th>500</th></tr></thead><tbody><tr><th>C<sub>2</sub></th><td>12.8</td><td>31.5</td><td>84.8</td><td>157.7</td><td>281.9</td><td>631.3</td><td>1446.6</td><td>4380.9</td></tr><tr><th>h<sub>1</sub></th><td>0.0</td><td>0.0</td><td>12.0</td><td>4.9</td><td>8.8</td><td>5.0</td><td>7.8</td><td>7.1</td></tr><tr><th>h<sub>2</sub></th><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.1</td><td>0.0</td><td>0.1</td><td>0.0</td></tr><tr><th>h<sub>3</sub></th><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.1</td><td>0.0</td><td>0.2</td><td>0.0</td></tr></tbody></table>

We see that all methods lead to merge patterns which are equivalent to within less than 1%, except for $\mathcal{C}_1$ which, as indicated earlier, can get as bad as 20% from optimal. It follows that Heuristic 3 appears to be the best choice available at the moment.

## 5. ADVICE TO THE DESIGNER OF A MERGE

In a manner of conclusion, we try to show some applications of our analysis to problems arising in the design of a merge routine.

Since the lower bound $k n \log n$ (see(10)) is a good approximation of $C_2$, we can define a "hardware merge speed" $\sigma$ of a given configuration by:

$$ \frac{1}{\sigma} = k = \min_{d \ge 2} \frac{\mathcal{C}_{A/M} (1 + \sqrt{d})^2 + 2 \mathcal{C}_T}{\log d} \quad (16) $$
The merge time of n initial runs of length $\lambda$ is then :

$$C_2(n) = \frac{\lambda}{\sigma} n \log n \quad (17)$$

and the "hardware merge speed" is a convenient tool for estimating the merge perfomance of a given hardware configuration. For example, (16) shows that doubling the memory size M has thus the same effect as reducing by half the access time.

In table 2 we compare the merge performances of three direct-access devices, each of which being used in configurations with a small (0.04 Megabyte), intermediate (0.1 MB) or large (1 MB) core memory. Each device is characterized by its access time $\mathcal{C}_A$ and its transfer rate $\mathcal{V}_T = 1/\mathcal{C}_T$ (figures are taken from CII and IBM user's manuals). For each memory size, table 2 shows the corresponding $\beta/a$, $d_{lim}$ and k of equation (16) as well as $C_2(n)$ for various values of n.

The length unit is the megabyte so that k and $\mathcal{C}_T$ are expressed in seconds per MB ; $C_2(n)$ is then the time in seconds of an optimal merge of n initial runs of size one MB.

<table><caption>Table 2</caption><caption>CII DISK PACK DIMAS 72282<br>U = 0.252 megabyte/sec.</caption><thead><tr><th>M</th><th>β/a</th><th>d<sub>lim</sub></th><th>k=1/σ</th><th>n</th><th>10</th><th>30</th><th>50</th><th>100</th><th>300</th></tr></thead><tbody><tr><td>0.04</td><td>3.43</td><td>6</td><td>19.79</td><td rowspan="3">C<sub>2</sub></td><td>480.0</td><td>2028.2</td><td>3892.6</td><td>9305.6</td><td>33975.0</td></tr><tr><td>0.1</td><td>8.58</td><td>8</td><td>10.34</td><td>239.6</td><td>1097.0</td><td>2033.2</td><td>4792.3</td><td>17875.7</td></tr><tr><td>1</td><td>85.80</td><td>32</td><td>3.47</td><td>95.4</td><td>354.5</td><td>698.1</td><td>1907.8</td><td>6241.3</td></tr></tbody></table>

<table><caption>IBM DISK PACK 3330<br>U = 0.8 megabyte/sec.</caption><thead><tr><th>M</th><th>β/a</th><th>d<sub>lim</sub></th><th>k=1/σ</th><th>n</th><th>10</th><th>30</th><th>50</th><th>100</th><th>300</th></tr></thead><tbody><tr><td>0.04</td><td>2.61</td><td>6</td><td>7.75</td><td rowspan="3">C<sub>2</sub></td><td>190.9</td><td>792.6</td><td>1533.1</td><td>3617.2</td><td>13360.0</td></tr><tr><td>0.1</td><td>6.53</td><td>7</td><td>3.90</td><td>91.4</td><td>407.0</td><td>763.2</td><td>1827.1</td><td>6694.0</td></tr><tr><td>1</td><td>65.27</td><td>26</td><td>1.20</td><td>31.6</td><td>123.2</td><td>249.7</td><td>632.7</td><td>2112.5</td></tr></tbody></table>

<table><caption>IBM DRUM 2301<br>U = 1.2 megabyte/sec.</caption><thead><tr><th>M</th><th>β/a</th><th>d<sub>lim</sub></th><th>k=1/σ</th><th>n</th><th>10</th><th>30</th><th>50</th><th>100</th><th>300</th></tr></thead><tbody><tr><td>0.04</td><td>7.75</td><td>8</td><td>2.32</td><td rowspan="3">C<sub>2</sub></td><td>53.9</td><td>244.3</td><td>454.8</td><td>1076.3</td><td>3994.7</td></tr><tr><td>0.1</td><td>19.38</td><td>12</td><td>1.36</td><td>31.6</td><td>157.7</td><td>281.9</td><td>631.3</td><td>2375.4</td></tr><tr><td>1</td><td>193.83</td><td>58</td><td>0.57</td><td>18.2</td><td>60.8</td><td>111.3</td><td>270.7</td><td>1127.5</td></tr></tbody></table>
This table shows that a small memory does not kill you if you have a fast device : the merge time with a drum connected to a 40 000 bytes memory is less than the merge time with a disk connected to a million bytes of core.

Finally, if one has to sort a long file, a compromise is to be found between the time spent for generating initial runs, and the time spent for merging them. If one provides analysis for the time taken by the generation phase in terms of the length of the runs thus obtained, the cost of the sort is :

$$ \text{"Cost of generating n initial runs"} + k L \log n \quad (18) $$

where L is the length of the file ; the initial cost depends on n, $L, \epsilon_A, \epsilon_T$ and M. Minimizing (18) should then allow one to determine the optimum number n of initial runs to be generated.

## 6. SUMMARY

In this paper we described algorithms and heuristics for computing optimal merge patterns together with analytic tools for evaluation and design of merge routines. This study should help the designer of a sorting routine in his choice of the adequate algorithm for generating the initial runs. When the runs generated are of very unequal lengths, the problem of finding algorithms or heuristics for computing optimal patterns is still open.
## ACKNOWLEDGMENT

The authors are indebted to Donald Knuth for his constant interest and for suggesting the proof of the upper-bound, in inequality (10).

## REFERENCES

[1] J.W. Graham, P.S. Kritzinger "A survey of sorting activity at Canadian computer installations". Canadian Data Systems. January 1973. 40-41.

[2] D.E. Ferguson. "Buffer allocation in merge sorting". Communications of the ACM 14,7. July 1971, 476-478.

[3] D.E. Knuth. "The art of computer programming" Vol 3
Addison Wesley. 1973, 361-378.

[4] D.E. Knuth. "The art of computer programming" vol 1
Addison Wesley. 1968, 401.

[5] L. Hyafil, F. Prusker, J. Vuillemin - Unpublished paper.

[6] M. Schlumberger, J. Vuillemin. "Optimal disk merge patterns". To appear in *Acta Informatica* - 1974.

[7] L. Hyafil, F. Prusker, J. Vuillemin. "An efficient algorithm for computing optimal disk merge patterns". To appear, 1974.

[8] N.A. Black. "Optimum merging from mass storage". *Communication of the ACM* 13, 12. December 1970, 745-749.