<p>Surprisingly, linear time in-place stable sort is possible with integer keys of <span class="math-container">$O(\log n)$</span> bit length.</p>
<p>An algorithm appeared in <a href="https://arxiv.org/abs/0706.4107" rel="nofollow noreferrer">Radix Sorting With No Extra Space</a> (Franceschini, Muthukrishnan, Patrascu 2007).  However:</p>
<ul>
<li>Their algorithm is complicated (though they give a simpler algorithm for the variation with writable keys).  Has a simpler account/algorithm ever appeared?</li>
<li>One case is left for the &quot;full paper&quot; in the full paper.  Has an extra-full version or other account of that case ever appeared? (The case is <span class="math-container">$\log^{o(1)} n$</span> (but more than <span class="math-container">$O(1)$</span>) distinct (frequent) keys.)</li>
</ul>
<p>Independently of the paper, but after reading <a href="http://hjemmesider.diku.dk/%7Ejyrki/Paper/KP1992bJ.pdf" rel="nofollow noreferrer">Stable Minimum Space Partitioning in Linear Time</a> (Katajainen and Pasanen 1992), I found a simpler algorithm for linear time in-place stable sort with integer keys of <span class="math-container">$O(\log n)$</span> 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.</p>
<p><i>Description (with additional details below):</i><br/>
• By doing stable sort on different parts of the key, it suffices to consider a universe of <span class="math-container">$n^ε$</span> keys.<br/>
• 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 <span class="math-container">$\log n$</span> bits) in constant time.<br/>
• Elements with rare keys can be sequestered or otherwise special-cased.  For example, we can move <span class="math-container">$\sqrt n$</span> elements to the end in <span class="math-container">$O(n)$</span> time using <span class="math-container">$O(\sqrt n)$</span> moves of a contiguous block coalescing the elements.<br/>
• If we have <span class="math-container">$d$</span> common keys, we can build some unit-cost RAM with <span class="math-container">$Θ(\log d)$</span> bits per cell.  A single cell can be made of <span class="math-container">$d^{Θ(1)}$</span> items, with its value being an appropriate function (allowing all cell values) of the key of the first item.<br/>
• To sort, we arrange the items into constant-key blocks of fixed size <span class="math-container">$k≥\log^2 n$</span>, 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 <span class="math-container">$k$</span> items with the same key, we write out the block and forget the items, while storing how other items were displaced by the block.<br/>
  - If <span class="math-container">$d$</span> is below (say) <span class="math-container">$\sqrt{\log n}$</span> (note: <span class="math-container">$\log^c n$</span> with <span class="math-container">$0&lt;c&lt;1$</span> also works), we start with a smaller <span class="math-container">$k$</span> (<span class="math-container">$O(\log^{1-c} n / \log \log n)$</span>) and store the data by packing microwords into <span class="math-container">$O(1)$</span> RAM words (which can be done using bit shifts).  Then, we repeatedly increase <span class="math-container">$k$</span> by treating blocks of items as single items.<br/>
  - For higher <span class="math-container">$d$</span>, we use the faster extra RAM.<br/>
• Using the main extra RAM, find and apply the desired permutation, and complete the sort.</p>
<p><i>Notes and additional details:</i><br/>
• &quot;In-place&quot; allows <span class="math-container">$O(1)$</span> RAM words (outside of the list), and the ability to swap two list items.<br/>
• The extra RAM setup is: find a large region not too dominated by one key (or complete the sort) <span class="math-container">$→$</span> sort it <span class="math-container">$→$</span> main extra RAM <span class="math-container">$→$</span> find a region with enough items for sufficiently many different keys <span class="math-container">$→$</span> sort it <span class="math-container">$→$</span> 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.<br/>
• For constructing the faster extra RAM, to get all cell values, <span class="math-container">$a$</span> * key % <span class="math-container">$p$</span> % <span class="math-container">$m$</span> should work (<span class="math-container">$a$</span> and <span class="math-container">$p$</span> depend on the set of keys; <span class="math-container">$m$</span> is the number of cell values and is not too large).  Alternatively, we can use <span class="math-container">$(h(A[\mathrm{key}])+h(B[\mathrm{key}]))$</span> % <span class="math-container">$m$</span> with <span class="math-container">$h$</span> chosen (for example, using a universal hashing family) to allow most cell values on the set of keys.<br/>
• The arrangement into <span class="math-container">$k$</span>-sized constant blocks here resembles counting sort, but is easier to use afterwards.  During the arrangement, we can store loc[key][i] --&gt; location of ith unwritten item for the key, and item[location] --&gt; key, i (or just i). In the arrays, location can be stored modulo <span class="math-container">$kd$</span>.  Keys are compressed using perfect hashing.<br/>
• The number of blocks is small enough for the computation of their permutation in the main extra RAM.  Also, blocks smaller than <span class="math-container">$k$</span> can be kept at the end, and sorted last.  If most items have the same key, we might not have <span class="math-container">$ω(n \log n / k)$</span> bits of extra RAM, but we can group those items together while recording how other blocks are permuted by this.  Alternatively, starting with <span class="math-container">$Ω(\log n)$</span> <span class="math-container">$k$</span>, we can repeatedly increase <span class="math-container">$k$</span> in <span class="math-container">$n^{Θ(1)}$</span> times until it is large enough.</p>
<p><i>Extensions:</i><br/>
• The above algorithm can be made to work when only the first <span class="math-container">$n^ε$</span> places (<span class="math-container">$Ω(1)$</span> <span class="math-container">$ε$</span>) in the list are random access, with the other items swapped in <span class="math-container">$Ω(n^{-ε}i)$</span>-sized blocks (at unit cost per item), where <span class="math-container">$i$</span> is index. The <span class="math-container">$n^{-ε}$</span> allows avoiding a logarithmic factor.<br/>
• 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 <span class="math-container">$d$</span> (where we use packing of microwords), we now first use the faster extra RAM to get constant blocks of size <span class="math-container">$k'=Ω(\log d)$</span> so that a key hash can be retrieved in <span class="math-container">$O(k')$</span> time.</p>
<p>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.</p>
<p>In practice, one would usually have a polynomial amount RAM (even <span class="math-container">$n^{1-ε}$</span> or <span class="math-container">$εn$</span> (outside of the list) if the list is in RAM), rather than <span class="math-container">$O(1)$</span> 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.</p>

CC BY-SA 4.0
2022-07-24T10:07:02.637Z
Sorry if I missed it, but what is your question?
Tassle
CC BY-SA 4.0
2022-07-24T15:21:37.063Z
@Tassle The two questions are in the bullet points at the top.
Dmytro Taranovsky
<ds.algorithms><reference-request><sorting>
Linear time in-place stable sort
Dmytro Taranovsky
# Linear time in-place stable sort

(Asked by: username_0 on 2022-07-20)

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](https://arxiv.org/abs/0706.4107) (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](http://hjemmesider.diku.dk/%7Ejyrki/Paper/KP1992bJ.pdf) (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 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.

**Tags:** ds.algorithms, reference-request, sorting

> **Comments:**
> **username_1**: Sorry if I missed it, but what is your question?  
> **username_0**: @username_1 The two questions are in the bullet points at the top.  

---

## 0 answers

