Information Technology Reference
In-Depth Information
account, as has the order among the
B
words in a block) is at most
ρ
=
B
, the binomial
coefficient. (To see this, observe that places for the
B
new (and indistinguishable) words in
the primary memory can be any
B
of the
M
indistinguishable places.) It follows that the
multi-comparison decision tree for every BTM comparison-based sorting algorithm on the
BTM has at most
n/B
vertices with at most
ρB
!
possible outcomes (vertices corresponding
to the first arrival of one of the blocks in primary memory) and that each of the other vertices
has at most
ρ
outcomes.
It follows that if a sorting algorithm executes
T
BTMsort
(
n
)
block I/O steps, the function
T
BTMsort
(
n
)
must satisfy the following inequality:
(
B
!)
n/B
M
B
T
BTMsort
(
n
)
≥
n
!
Using the approximation to
n
!
giveninLemma
11.8.1
, the upper bound of
(
M/B
)
B
e
B
on
B
derived in Lemma
10.12.1
,andthefactthat
T
n/B
, we have the desired conclusion.
An upper bound is obtained by extending the standard merging algorithm to blocks of
keys. The merging algorithm is divided into phases, an initialization phase and merging
phases, each of which takes
(
2
n/B
)
I/O operations. In the initialization phase, a set of
n/M
sorted sublists of
M
keys or
M/B
blocksisformedbybringinggroupsof
M
keys into
primary memory, sorting, and then writing them out to secondary memory. In a merging
phase,
M/B
sorted sublists of
L
blocks (
L
=
M/B
in the first merging phase) are merged
into one sorted sublist of
ML/B
blocks, as suggested in Fig.
11.16
. The first block of keys
(those with the smallest values) in each sublist is brought into memory and the
B
smallest
keys in this set is written out to the new sorted sublist that is being constructed. If any
block from an input sublist is depleted, the next block from that list is brought in. There
is always sufficient space in primary memory to do this. Thus, after
k
phases the sorted
sublists contain
(
M/B
)
k
blocks. When
(
M/B
)
k
≥
≥
n/B
, the merging is done. Thus,
(
2
n/B
)
log
2
(
n/B
)
/
log
2
(
M/B
)
I/O operations are performed by this algorithm.
B
Secondary Memory
...
L
L
L
Primary
Memory
...
Figure 11.16
The state of the block merging algorithm after merging four blocks. The algo-
rithm merges
M/B
sublists, each containing
L
blocks of
B
keys.
M/B
Secondary Memory
Search WWH ::
Custom Search