Explain the external sort-merge algorithm with suitable example.

 External Sort-Merge Algorithm

Sorting of relations that do not fit in memory is called external sorting. The most commonly used technique for external sorting is the external sort-merge algorithm. Let M denote memory size (in pages).

1. Create sorted runs. Initialize i=0.

Repeat the following till the end of the relation (Let the final value of i be N)

a) Read M blocks of relation into memory

b) Sort the in-memory blocks

c) Write sorted data to run R

d) i=i+1

2.. Merge the runs (N-way merge). We assume that N<M. 

Use N blocks of memory to buffer input runs (one block per run), and one block to buffer output.

b. Repeat the following steps until all input buffer pages are empty:

i. Select the first record (in sort order) among all buffer pages 

ii. Write the record to the output buffer. If the output buffer is full write it to disk. 

iii. Delete the record from its input buffer page. If the buffer page becomes empty then read the next block (if any) of the run into the buffer.

Figure: External sorting using sort-merge.

The figure illustrates the steps of the external sort-merge for an example relation. For illustration purposes, we assume that only one tuple fits in a block (f, = 1), and we assume that memory holds at most three blocks. During the merge stage, two blocks are used for input and one for output.

Cost Analysis of external Sort-Merge

Let br denote the number of blocks containing records of relation r. The initial number of runs =[br/M].

Since the number of runs decreases by a factor of M. 1 in each merge pass;