Merge-sort analysis by matrix techniques
Charles E. Radke · IBM Systems Journal · 1966
A classification of merge-sorts has been introduced in which members of Class Ia for i = 0 and i = k − 1 agree with Carter's definition of polyphase and cascade merge-sorts. For 0 < i < k − 1, the defined merge-sorts are classified in the general category of compromise merge-sorts. Class Ia and the defined larger Class I merge-sorts are shown to have interesting properties, the most important being that members of these classes can be characterized by a single matrix. Interpreted, this property indicates that the particular merge can go to completion using the same procedure throughout the merge. This property defines a merge going to proper completion. The introduction of matrix descriptions of Classes I and Ia merge-sorts is useful since methods of matrix manipulation are well known. By defining new operators for the matrices, it is shown how patterns of ascending and descending sequences required as a result of the presort phase can be determined.