الفهرس 
AcknowledgementOnly 14 pages are availabe for public view
 |  | from | 87 |  |  |
| | | from | 87 | | |
Abstract
This thesis deals with the problem of merging two files one has n elements the other has m elements, fyom the view point of introducing an algorithm which as worst case number of comparisons less than the known algorithms. It also deals with the problem of merging if parallel processing is used.
First the problem is defined with a description of the known merging algo¬rithms, then an algorithm is presented which beats those algorithms in the worst case behavior. In order to analyze such an algorithm first a set of known results are presented then lemmas and theorems used in the analysis are outlined with their proofs.
The algorithm extends the ideas used in previous algorithms by presenting a powerful set of methods that allow the result of every comparison done to be fully used. The algorithm also uses the known optimal results on merging m elements with n elements if m < 3. The algorithm is presented with the aid of pseudo code and explanatory diagrams, and divided into basic blocks which are linked together finally to form the algorithm. Methods and techniques that allow every block to be extended are described and applied to the algorithm.
The other problem presented deals with the efficiency of parallel merging algorithms. An algorithm is presented which is so close to be work optimal. First a variant of binary merge algorithm which depends on parallel selection of probes is presented then the idea is extended to the parallel case.
Finally conclusions are presented with a discussion of ways to extend this work and a description of some open problems.