## 4 Novel \(O(\log_{2}N)\) fully-balanced Redistribution
### Algorithmic Details and Theorems
#### 4.2.1 Rotational Nearly Sort
Therefore, each particle will be shifted \(O(\log_{2}N)\) times, each time by an increasing power-of-two number of positions, and, since \(\mathbf{shifts}\) gets updated in \(O(1)\), Algorithm 2 achieves an \(O(\log_{2}N)\) time complexity. Furthermore, as long as no particle to be copied collides with or gets past another one, Algorithm 2 always achieves (9), since the shifts to perform will progressively decrease, whereas (12) will always hold. Lemma 1 and Corollary 1 prove that collisions and overtaking (defined in the following definitions) can never occur. **Definition 3** (Collisions). : _Let \(\mathbf{x}^{i}\) be a particle having \(\mathbf{ncopies}^{i}\geq 1\), and \(\mathbf{x}^{i}\) be a particle having \(\mathbf{ncopies}^{j}\geq 1\), with \(j=i+dist\), where \(0<dist<N-1\). A collision would occur if dist is a power-of-two number, \(\mathbf{x}^{i}\) is rotating to the left by dist and \(\mathbf{x}^{i}\) stays where it is. More formally, a collision occurs if the total number of rotations that \(\mathbf{x}^{i}\) must perform has significant bit (i.e., the bit corresponding to dist rotations) equal to \(1\), while the same bit of the number of rotations that \(\mathbf{x}^{i}\) must perform is \(0\). The same definition can be applied to collisions when rotations are performed to the right if \(\mathbf{x}^{i}\) is rotating to the right (and, hence, have significant bit equal to \(1\)) and \(\mathbf{x}^{i}\) is not rotating (and, hence, have significant bit equal to \(0\))._  
**Definition 4** (Overtaking). : _Let \(\mathbf{x}^{i}\) again be a particle having \(\mathbf{ncopies}^{i}\geq 1\), and \(\mathbf{x}^{i}\) again be a particle having \(\mathbf{ncopies}^{j}\geq 1\), with \(j=i+dist\), where \(0<dist<N-1\). The particle \(\mathbf{x}^{i}\) can overtake \(\mathbf{x}^{i}\) if it is rotating to the left by a power-of-two number greater than dist while \(\mathbf{x}^{i}\) stays where it is. The same problem occurs when rotations are performed to the right, if \(\mathbf{x}^{i}\) is rotating to the right by a power-of-two number greater than dist while \(\mathbf{x}^{i}\) stays where it is._  
**Lemma 1**. : _During the \(k\)-th iteration of Rotational Nearly Sort, \(\forall k=1,2\),..., \(\log_{2}P\), a particle \(\mathbf{x}^{i}\), having \(\mathbf{ncopies}^{j}\geq 1\) and rotating to the left by \(\frac{N}{P}2^{k-1}\) positions, can never collide with a particle \(\mathbf{x}^{i}\), having \(\mathbf{ncopies}^{i}\geq 1\) and \(j=i+\frac{N}{P}2^{k-1}\)._  
Proof of Lemma 1.: At the \(k\)-th iteration, particle \(\mathbf{x}^{i}\) has \(\mathbf{shifts}^{i}\) remaining rotations to the left, whereas \(\mathbf{x}^{i}\) has \(\mathbf{shifts}^{j}\). Therefore, the necessary and sufficient condition for collisions, defined in Definition 3, can be restated for Rotational Nearly Sort by checking whether the following logical condition  
\[\left(\left(\mathbf{shifts}^{i}\&\frac{N}{P}2^{k-1}\right)=0\right)\wedge\left( \left(\mathbf{shifts}^{i}\&\frac{N}{P}2^{k-1}\right)>0\right) \tag{13}\]  
is true, which corresponds to checking whether the significant bit of \(\mathbf{shifts}^{i}\) is \(0\) and the significant bit of \(\mathbf{shifts}^{i}\) is \(1\). This condition can also be rearranged as follows:  
\[\left(\left(\mathbf{shifts}^{i}\&\frac{N}{P}2^{k-1}\right)=0\right)\wedge\left( \left(\left(\mathbf{shifts}^{i}+\mathbf{zeros}^{i+1:j-1}\right)\&\frac{N}{P}2^ {k-1}\right)>0\right) \tag{14}\]  
where \(\mathbf{zeros}^{i+1:j-1}\) is the number of \(0\)s in \(\mathbf{ncopies}\) between positions \(i\) and \(j\) excluded. Since Rotational Nearly Sort performs rotations using an LSB-to-MSB strategy, it is easy to infer that the bits to the right of the significant one at this iteration (i.e., bit \(k-1\)) are all \(0\). This means that, if the significant bit of \(\mathbf{shifts}^{i}\) is \(0\), the only condition that would make (14) true would be \(\mathbf{zeros}^{i+1:j-1}=\frac{N}{P}2^{k-1}\).