Internal Sorting Using A Minimal Tree Merge Strategy
Original Publication Date: 1980-Feb-01
Included in the Prior Art Database: 2005-Feb-13
An internal sorting algorithm is described which implements a minimal tree merge strategy. The algorithm can be used for either straight merge sorting or natural merge sorting. The number of comparisons is always less than nlog(2)n, ranging from l/2nlog(2)n to n(log(2)n-1) for straight merge sorting, and from n to n(log(2)n-1/2) for natural merge sorting. The algorithm is particularly well suited for sorting an unspecified number of items represented by a linkedlist, requiring only 2x((see original)log(2)n+l) extra storage words.