Internal Sorting Using a Minimal Tree Merge Strategy
Leigh R. Power · ACM Transactions on Mathematical Software · 1980
An internal sorting algorithm whwh implements a mmimal tree merge strategy is described.It can be used for either strmght merge sorting or natural merge sorting.The number of comparisons is always less than n log2n, ranging from ½n log2n to n(log2n -1) for straight merge sorting, and from n to n(log2n -½)for natural merge sorting.The algorithm Is particularly well stated for sorting an unspecified number of Items represented by a linked list, requiring only 2 × (llog2n + 1) extra storage words The sequencing of merges is governed by the lengths of input and intermediate stnngs The heads of ordered strings are maintained m an array which contains two slots for each length range, where a string's length range is defined as [log2 of the length of the strmg.Dunng the first pass of this algorithm, merges are restricted to strings from equal length ranges; a merge is performed whenever a third string for a given length range is created.The second pass merges all remaining strings, starting with the shortest string first.Empn~ical comparisons are presented of straight versus natural merge sorting.Several slmdar algorithms are also discussed.