## 4 Novel \(O(\log_{2}N)\) fully-balanced Redistribution
### Algorithmic Details and Theorems
#### 4.2.1 Rotational Nearly Sort
That is, however, impossible, because, in this case, there are only \(i+\frac{N}{P}2^{k-1}-1\) memory slots between \(i\) and \(j\), which means that:  
\[\mathbf{zeros}^{i+1:j-1}\leq j-i-1=\frac{N}{P}2^{k-1}-1<\frac{N}{P}2^{k-1} \tag{15}\]  
During the \(k\)-th iteration of Rotational Nearly Sort, \(\forall k=1,2,...,\log_{2}P\), a particle \(\mathbf{x}^{i}\), having \(\mathbf{ncopies}^{i}\geq 1\) and rotating to the left by \(\frac{N}{P}2^{k-1}\) positions, can never overtake a particle \(\mathbf{x}^{i}\), having \(\mathbf{ncopies}^{i}\geq 1\) and \(i<j<i+\frac{N}{P}2^{k-1}\). Proof of Corollary 1.: Lemma 1 can automatically prove Corollary 1 because, once again, (14) is true only if \(\mathbf{zeros}^{i+1:j-1}=\frac{N}{P}2^{k-1}\). However, in this case, \(j<i+\frac{N}{P}2^{k-1}\), and hence:  
\[\mathbf{zeros}^{i+1:j-1}\leq j-i-1<j-i<\frac{N}{P}2^{k-1} \tag{16}\]  
Rotational Split  
Given an array of \(N\) particles, \(\mathbf{x}\), and their copies to be created, \(\mathbf{ncopies}\), whose elements are nearly sorted according to (9), and evenly distributed across the \(P\) cores of a DM, Algorithm 4 (performed by each core \(p\), \(\forall p=0,1,...,P-1\)) describes the steps to shift and/or safely split the elements in \(\mathbf{x}\) and \(\mathbf{ncopies}\) to achieve properties (10) and (11), and performs that in \(O(\log_{2}N)\) parallel time for \(P=N\). Proof of Theorem 2.: Let \(\mathbf{csum}\in\mathbb{Z}^{N}\) be the inclusive cumulative sum of \(\mathbf{ncopies}\). As mentioned in the previous section, the cumulative sum achieves an \(O(\frac{N}{P}+\log_{2}P)\) time complexity for any \(P\leq N\). To achieve (10), we want to move the particles to the right to have \(\mathbf{ncopies}^{i}-1\) gaps after each index \(i\), such that \(\mathbf{ncopies}^{i}>0\). It can be inferred that the minimum required number of shifts to the right that the \(i\)-th particle must perform is:  
\[\mathbf{min\_shifts}^{i}=\sum_{z=0}^{i-1}(\mathbf{ncopies}^{z}-1)=\mathbf{csum }^{i}-\mathbf{ncopies}^{i}-i \tag{17}\]  
However, (10) alone does not guarantee (11). This is because, for each particle \(\mathbf{x}^{i}\) that must be copied more than once, we are rotating all of its copies by the same minimum number of positions, and we are not considering that some of these copies could be split and rotated further to also fill in the gaps that a strategy for (10) alone would create. Therefore, we also consider the maximum number of rotations that any copy of \(\mathbf{x}^{i}\) has to perform, without causing collisions. Since (10) aims to creating \(\mathbf{ncopies}^{i}-1\) gaps for each \(i\), such that \(\mathbf{ncopies}^{i}>0\), that number is:  
\[\mathbf{max\_shifts}^{i}=\mathbf{min\_shifts}^{i}+\mathbf{ncopies}^{i}-1= \mathbf{csum}^{i}-i-1 \tag{18}\]  
Therefore, the key idea is to consider \(\mathbf{min\_shifts}^{i}\) and \(\mathbf{max\_shifts}^{i}\) in binary notation and use their bits to rotate the particles accordingly, from the MSB to the LSB. This corresponds to using a top-down binary tree structure of \(\log_{2}P\) stages. At each stage \(k\) of the tree (for \(k=1,2,...,\log_{2}P\)), any core with rank \(p\) sends particles \(N2^{-k}\) positions ahead to its partner with rank \(p+\frac{P}{2^{k}}\). At each \(k\)-th stage, we check the MSB of both \(\mathbf{min\_shifts}^{i}\) and \(\mathbf{max\_shifts}^{i}\) to infer \(\mathbf{copies\_to\_send}^{i}\), the number of copies of \(\mathbf{x}^{i}\) that must rotate by \(N2^{-k}\) positions. For each \(\mathbf{x}^{i}\), three possible scenarios may occur:  
None of its copies must move;  
All of them must rotate;  
Some must split and shift, and the others must not move. Trivially, the copies will not move if the MSB of \(\textbf{max\_shifts}^{i}\) is 0, which also implies that the MSB of \(\textbf{min\_shifts}^{i}\) is 0, since \(\textbf{min\_shifts}^{i}\leq\textbf{max\_shifts}^{i}\) at all stages. If both MSBs are 1, we send \(\textbf{copies\_to\_send}^{i}=\textbf{ncopies}^{i}\) copies of \(\textbf{x}^{i}\).