Report Number: CS-TR-74-470
Institution: Stanford University, Department of Computer Science
Title: Stable sorting and merging with optimal space and time
Author: Trabb-Pardo, Luis I.
Date: December 1974
Abstract: 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.