The Algorithm in a Nutshell
Using an evenly distributed sample a1, . . . , af of size Θ(n/(log n)4), split the remaining elements into some segments σ0, σ1, . . . , σf , of length Θ((log n)4) each, so that all elements in the segment σk satisfy ak ≤ a ≤ ak+1. The sorted array is obtained by forming the sequence σ’0 , a1, σ’1 , . . . , af , σ’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 σ0. 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)3), 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 ak 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)2) 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.
- sasikalac on A Math Primer for Gentry’s Fully Homomorphic Encryption
- Srikanth on Using jqGrid with ASP.NET MVC: Deleting Records
- Majed on join in LINQ to SQL and LINQ to Entities Considered Messy, Redundant
- DAVID on Troubleshooting Entity Framework Connection Strings
- Fede Torre on Faking a placeholder Attribute for an Editable div, and Some CSS Tricks