Stable Sorting in Asymptotically Optimal Time and Extra Space

Publisher Website
Google Scholar
Abstract
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

This publication has 1 reference indexed in Scilit: