Surprisingly, linear time in-place stable sort is possible with integer keys of $O(\log n)$ bit length.
An algorithm appeared in Radix Sorting With No Extra Space (Franceschini, Muthukrishnan, Patrascu 2007). However:
- Their algorithm is complicated (though they give a simpler algorithm for the variation with writable keys). Has a simpler account/algorithm ever appeared?
- One case is left for the "full paper" in the full paper. Has an extra-full version or other account of that case ever appeared? (The case is $\log^{o(1)} n$ (but more than $O(1)$) distinct (frequent) keys.)
Independently of the paper, but after reading Stable Minimum Space Partitioning in Linear Time (Katajainen and Pasanen 1992), I found a simpler algorithm for linear time in-place stable sort with integer keys of $O(\log n)$ bit length (below). I like how it ties multiple ideas, and the interplay of different available resources. The above questions (while not technically about the below algorithm) may clarify the extent to which it is new.
Description (with additional details below):
• By doing stable sort on different parts of the key, it suffices to consider a universe of $n^ε$ keys.
• After sorting a part of the list, we can partially rearrange it to effectively get extra RAM with the ability to get or set a bit (as opposed to $\log n$ bits) in constant time.
• Elements with rare keys can be sequestered or otherwise special-cased. For example, we can move $\sqrt n$ elements to the end in $O(n)$ time using $O(\sqrt n)$ moves of a contiguous block coalescing the elements.
• If we have $d$ common keys, we can build some unit-cost RAM with $Θ(\log d)$ bits per cell. A single cell can be made of $d^{Θ(1)}$ items, with its value being an appropriate function (allowing all cell values) of the key of the first item.
• To sort, we arrange the items into constant-key blocks of fixed size $k≥\log^2 n$, allowing one smaller block per key at the end, and without reordering items with the same key. For this, we scan the list from left to right, and when we get $k$ items with the same key, we write out the block and forget the items, while storing how other items were displaced by the block.
- If $d$ is below (say) $\sqrt{\log n}$ (note: $\log^c n$ with $0<c<1$ also works), we start with a smaller $k$ ($O(\log^{1-c} n / \log \log n)$) and store the data by packing microwords into $O(1)$ RAM words (which can be done using bit shifts). Then, we repeatedly increase $k$ by treating blocks of items as single items.
- For higher $d$, we use the faster extra RAM.
• Using the main extra RAM, find and apply the desired permutation, and complete the sort.
Notes and additional details:
• "In-place" allows $O(1)$ RAM words (outside of the list), and the ability to swap two list items.
• The extra RAM setup is: find a large region not too dominated by one key (or complete the sort) $→$ sort it $→$ main extra RAM $→$ find a region with enough items for sufficiently many different keys $→$ sort it $→$ faster extra RAM. Note that a majority element can be found in linear time and constant space. Using a portion of the sorted list, extra RAM is also available for the merge at the end of the sort.
• For constructing the faster extra RAM, to get all cell values, $a$ * key % $p$ % $m$ should work ($a$ and $p$ depend on the set of keys; $m$ is the number of cell values and is not too large). Alternatively, we can use $(h(A[\mathrm{key}])+h(B[\mathrm{key}]))$ % $m$ with $h$ chosen (for example, using a universal hashing family) to allow most cell values on the set of keys.
• The arrangement into $k$-sized constant blocks here resembles counting sort, but is easier to use afterwards. During the arrangement, we can store loc[key][i] --> location of ith unwritten item for the key, and item[location] --> key, i (or just i). In the arrays, location can be stored modulo $kd$. Keys are compressed using perfect hashing.
• The number of blocks is small enough for the computation of their permutation in the main extra RAM. Also, blocks smaller than $k$ can be kept at the end, and sorted last. If most items have the same key, we might not have $ω(n \log n / k)$ bits of extra RAM, but we can group those items together while recording how other blocks are permuted by this. Alternatively, starting with $Ω(\log n)$ $k$, we can repeatedly increase $k$ in $n^{Θ(1)}$ times until it is large enough.
Extensions:
• The above algorithm can be made to work when only the first $n^ε$ places ($Ω(1)$ $ε$) in the list are random access, with the other items swapped in $Ω(n^{-ε}i)$-sized blocks (at unit cost per item), where $i$ is index. The $n^{-ε}$ allows avoiding a logarithmic factor.
• If we do not have multiplication (or '/' or '%', but shifts are still allowed), this limits hashing, but we can still build the faster extra RAM by using locations based on tuples of keys (the work area), integers encoded by keys (with arithmetic (using look-up tables) and addressing without decoding), and sequential movement of groups of items to and from the work area. If we source the RAM from one region, some common keys might not be built in, but we can map the keys to pairs of keys. For small $d$ (where we use packing of microwords), we now first use the faster extra RAM to get constant blocks of size $k'=Ω(\log d)$ so that a key hash can be retrieved in $O(k')$ time.
The authors of the paper in the question, instead of the faster extra RAM, use 'pseudo pointers', which adds complexity. They also do not use the fixed-size constant blocks. Their model does not use multiplication. I found their paper after I completed the main algorithm, but before the no-multiplication extension.
In practice, one would usually have a polynomial amount RAM (even $n^{1-ε}$ or $εn$ (outside of the list) if the list is in RAM), rather than $O(1)$ words, avoiding the need for the above extra RAM, and one would also consider parallelism and cache locality. Still, theoretical results are important for our understanding.
