Stable Sorting in Asymptotically Optimal Time and Extra Space
Edward C. Horvath · Journal of the ACM · 1978
A stable sorting algonthm is one which does not permute the relative order of records which have equal keys.In The Art of Computer Programming, Vol 3, Exercise 5 5-3, Knuth poses the problem of finding a stable sorting algorithm which requires less than O(N ~2) time to sort N records, for arbitrary N, and which also requires no more than O(log N) bits of extra space (space in excess of that required to hold the N records)Section 1 shows that a stable sorting algorithm may be derived directly from a stable merging algorithm, and thereafter this paper is restricted to stable merging algorithms.Section 2 defines the concept of a contlguent, and shows that a conttguent-forming algonthm may be used as the basis for a stable merging algorithm.A class of contiguent-formmg algorithms which exhibit a space/time tradeoff is presented In the extremes, one algorithm in the class gives rise to a stable merge requiring O(N) time and O(N log N) bits of extra space, another algorithm reqmres O(N log N) Ume and O(log N) bits of extra space to merge Section 3 describes the Stable Kronrod Merge, which reqmres O(N) time and O(log N) bits of extra space, but is not applicable to all cases.Section 4, however, shows how the Stable Kronrod Merge may be combined with contlguent-formmg algorithms to yield a generally applicable class of stable merging algorithms.One algorithm in the class is shown to require O(N) time and O(log N) bRs of extra space to merge Finally, Section 5 places this work within the context of other work on this problem, both current and future KEY WORDS AND PHRASES stable sorting, stable merging, contiguent CR CATEGORIES" 5 31 Recent work by Dewar [1] includes a stable merging algorithm which runs in time O(N ~/2) and in extra space O(log N) bits.Rwest [10] has found a stable sorting algorithm which requires time O(N log 2 N) in the average case and O(log 2 N) extra space (hisGeneral permission to make fair use in teaching or research of all or part of this matenal is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyright notice is given and that reference is made to the pubhcatlon, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permlssmn as does republication, or systematic or multiple reproduction