## 4 Novel \(O(\log_{2}N)\) fully-balanced Redistribution
### Algorithmic Details and Theorems
#### 4.2.1 Rotational Nearly Sort
However, if only the MSB of \(\textbf{max\_shifts}^{i}\) is equal to 1, \(\textbf{copies\_to\_send}^{i}<\textbf{ncopies}^{i}\). The number of copies to split is equal to how many of them must be placed from position \(i+N2^{-k}\) onwards to achieve a perfect workload balance. This is equivalent to computing how many copies make  
\[\textbf{csum}^{i}>i+N2^{-k}\]  
Therefore, if only the MSB of \(\textbf{max\_shifts}^{i}\) is equal to 1, we send  
\[\textbf{copies\_to\_send}^{i}=\textbf{csum}^{i}-i-N2^{-k} \tag{19}\]  
copies of \(\textbf{x}^{i}\) and we keep the remaining ones where they were. Here, as in Section 4.2.1, particles to be rejected are sent if the MSB of \(\textbf{max\_shifts}^{i}\) is 0 in order to keep all cores equally busy. This phase takes an \(O(\frac{N}{P}\log_{2}P)\) time complexity, because each core sends or receives \(\frac{N}{P}\) particles at every stage. However, to ensure a logarithmic time complexity, one needs to update \(\textbf{csum}\), \(\textbf{min\_shifts}\) and \(\textbf{max\_shifts}\) in \(O(\frac{N}{P})\). This can be achieved if the cores send  
Figure 3:0  
where \(s\) is the index of the first particle to send, having \(\textbf{ncopies}^{s}>0\). As long as no particle overwrites or moves past another one (which is proven to be impossible by Lemma 2), each core \(p\) can safely see the received \(starter\) as  
Figure 3:1  
and use it to re-initialize \(\textbf{csum}\) and update it in \(O(\frac{N}{P})\) as \(\textbf{csum}^{i}=\textbf{csum}^{i-1}+\textbf{ncopies}^{i}\)\(\forall i=p\frac{N}{P}+1,...,(p+1)\frac{N}{P}-1\). This strategy guarantees \(\textbf{csum}\) is always correct for at least any index \(i\), such that \(\textbf{ncopies}^{i}>0\), i.e., those indexes we require to be correct. Once \(\textbf{csum}\) is updated, Equations (17) and (18) are embarrassingly parallel. If \(P<N\), after \(\log_{2}P\) stages, the cores perform a leaf stage. Here, for each particle, we perform inter-core shifts or splits and shifts only if there is any copy to be sent to the neighbor; this is equivalent to checking if  
Figure 3:2  
where \((p+1)\frac{N}{P}\) is the first global index in the neighbor's memory. Arrays of 0s are again sent when no inter-core shifts are needed. We also consider internal shifts only if \(\textbf{min\_shifts}^{i}>0\), in order to both make room to receive particles from the neighbor, \(p-1\), and guarantee (10). This leaf stage takes \(O(\frac{N}{P})\) because \(\frac{N}{P}\) particles are sent or received. It is easy to infer that \(\textbf{min\_shifts}^{i}<N-1\) and \(\textbf{max\_shifts}^{i}\leq N-1\), as a particle copy could at most be shifted, or split and shifted from the first to the last position. Both \(\textbf{min\_shifts}^{i}\) and \(\textbf{max\_shifts}^{i}\) can be represented in base-2 by \(\log_{2}N\) bits. Therefore, as also anticipated above, only up to \(\log_{2}N\) messages are required, which means that the achieved time complexity of Algorithm 4 is \(O(\log_{2}N)\). Furthermore, the particles are progressively split according to the MSBs of \(\textbf{min\_shifts}^{i}\) and \(\textbf{max\_shifts}^{i}\), until they are split according to (21). Hence, after the final leaf stage, the first and last element of \(\textbf{csum}\) in the memory of each core will necessarily meet the following two requirements:  
Figure 3:3  
which, if subtracted, automatically proves (11). **Lemma 2**. : _Given a nearly sorted input \(\mathbf{ncopies}\), at the \(k\)-th iteration of Rotational Split, \(\forall k=1,2,...,\log_{2}P\), a particle \(\mathbf{x}^{i}\), having \(\mathbf{ncopies}^{i}\geq 1\) and rotating to the right by \(N2^{-k}\) positions, can never collide with or get past a particle \(\mathbf{x}^{i}\), having \(\mathbf{ncopies}^{j}\geq 1\) and \(j=i+dist\) with \(1\leq dist\leq N2^{-k}\)._  
Proof of Lemma 2.: This lemma can be proved in two possible complementary cases:  
1. There are one or more zeros between \(i\) and \(j\);
2. There are no zeros between \(i\) and \(j\).