Craig Stuntz’s Weblog

This month’s issue of the Journal of the ACM (subscription) presents an algorithm for in-place sorting which claims at worst O(n log n) comparisons and O(n) moves. From the paper:

The Algorithm in a Nutshell

Using an evenly distributed sample a₁, . . . , a_f of size Θ(n/(log n)⁴), split the remaining elements into some segments σ₀, σ₁, . . . , σ_f , of length Θ((log n)⁴) each, so that all elements in the segment σ_k satisfy a_k ≤ a ≤ a_k+1. The sorted array is obtained by forming the sequence σ’₀ , a₁, σ’₁ , . . . , a_f , σ’_f, where σ’_k denotes the segment σ_k in sorted order. To sort σ_k , use a modified heapsort, based on a heap structure in which the internal nodes have Θ((log n)^4/5) sons. This results in a constant number of moves per each element extracted from the heap.

Since an evenly distributed sample is hard to find, the sample grows dynamically, as the computation demands. Initially, the sample is empty, with f = 0. That is, all elements are transported, one after another, into the segment σ₀. Whenever, in the course of the computation, some segment σ_k becomes “too large,” halve this segment into two segments of equal length. The median element of the original segment is inserted in the proper position of the sample, so that the sample remains sorted. To minimize the number of moves required for insertions in the sample, the sample is sparsely distributed in a block of size Θ(n/(log n)³), in such a way that we do not lose the advantage of a quick binary search over the sample elements. Whenever required, a local density of the sample elements in the block is eliminated by redistributing the sample more evenly, which does not happen “too often.” To avoid the corresponding rearrangement of segments, we use also a pointer structure, connecting each sample element a_k with the corresponding segment σ_k . That is, only pointers are moved, the segments stay motionless in a separate workspace.

However, an in-place algorithm does not have an additional buffer array of size 3n, required for the sample and the segments, nor P ≈ Θ(n/(log n)²) bits, required for pointers. The bits are “created” at the very beginning by a modified heapsort. This initial routine collects the smallest and the largest P elements into blocks Π_L and Π_R placed, respectively, at the beginning and at the end of the array, which leaves an unsorted block A’ in between. Then, the jth bit can be encoded by swapping the jth element in Π_L with the j th element in Π_R.

To “create” a buffer for sorting the block A of length n, select the element b^≤ of rank [n'/4] and partition A into blocks A_< and B_≥, using b^≤  as a pivot. Then sort the block A_<, using B_≥ as an empty buffer array. (We can test if a given location contains a buffer element, by a single comparison with b^≤ . Before an “active” element is moved to a new location, one buffer element escapes from this location to the current location of the “hole.”) After sorting A_< we iterate, focusing on B_≥ as a new block A’. After O(log n) iterations, we are done.

Share This | Email this page to a friend