The recent results for merging developed by the authors are being described. Namely, it is dealt with
| – |
-a fast stable merging, which works in linear time and in O(N1/2) space (N is the total number of merged items). A new algorithm for such merging is given. The version of it for unstable merging requires just O(1)-space;
|
| – |
-a fast stable merging, which works in slightly nonlinear time and with variable workspace for merging. This algorithm is a thorough revision of that of Dudzinski and Dydek. O(1)-space version of this algorithm is discussed, too.
|
The experimental evaluation of these algorithms proved that they are the fastest in the corresponding classes.
Keywords Merging - space and time complexity - algorithms