External Sorting

Sorting a collection of records on some (search) key is a very useful operation. When the data to be sorted is too large to fit into available main memory, we need to use an external sorting algorithm. Such algorithms seek to minimize the number of disk accesses.

Minibase supports external merge sort (see the text for a full description) :

Suppose we have M buffer pages available in memory, and we need to sort a large file with, say, N pages. There are two passes for the external sort.

1. In Pass 0, read in M pages at a time and sort internally to produce ceil(N/M) runs of M pages each (except the last run, which may contain fewer pages). Runs are held in temporary heap files.
2. In Passes i = 1, 2, ..., use M - 1 buffer pages for input, and use the remaining page for output; thus you do a M - 1 way merge in each pass.

The public interface for the external sorting utility is available here.

Back to the List of Components
Back to the Minibase Home Page