Report Number: CS-TR-74-470
Institution: Stanford University, Department of Computer Science
Title: Stable sorting and merging with optimal space and time bounds.
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/74/470/CS-TR-74-470.pdf