Stable Sorting and Merging with Optimal Space and Time Bounds

This work introduces two algorithms for stable merging and stable sorting of files. The algorithms have optimal worst case time bounds, the merge is linear and the sort is of order $n \log n$. Extra storage requirements are also optimal, since both algorithms make use of a fixed number of pointers. Files are handled only by means of the primitives exchange and comparison of records and basic pointer transformations.