# Optimal Algorithms for Sorting Permutations with Brooms
## 4 Sorting Permutations with a Double Broom
### Analysis of \(A_{db}\)  
Let \(T_{db}\) be the total number of swaps performed in \(A_{db}\). We first consider step 4 of our algorithm. For \(S_{L}\), let \(C_{NT}^{S_{L}}\) be the non trivial cycles and \(n_{S}S_{L}\) be the number of markers in these cycles. Similarly, for \(S_{R}\), let \(C_{NT}^{S_{R}}\) be the non trivial cycles and \(n_{S}^{S_{R}}\) be the number of markers in these cycles. As these markers retain their relative positions till Step 4 of our algorithm, our total number of swaps \(T_{S_{R},S_{L}}\) in Step 4 will be:  
\[T_{S_{R},S_{L}}=C_{NT}^{S_{L}}+n_{S}^{S_{L}}+C_{NT}^{S_{R}}+n_{S}^{S_{R}}.\]  
Let \(T_{R}\) and \(T_{L}\) be the total number of swaps carried out in Step 1 and Step 2 respectively. To analyse \(T_{R}\) and \(T_{L}\), we allocate each of its swaps to closest star marker residing on the path and involved in the swap. Then,  
\[T_{R}=\sum_{S_{min}^{R}}T(S_{min}^{R}),\]  
where \(T(S_{min}^{R})\) is the number of swaps allocated to closest star marker \(S_{min}^{R}\). For \(S_{min}^{R}\), define \(D(S_{min}^{R})\) to be the distance from a star leaf to \(S_{min}^{R}\)'s home. With reference to the initial configuration state of the markers, let \(R(S_{min}^{R})\) be the number of markers smaller than \(S_{min}^{R}\) and on the right of \(S_{min}^{R}\). \[T_{L}=\sum_{S_{min}^{L}}T(S_{min}^{L}).\]  
Similarly, for \(S_{min}^{L}\), define \(D(S_{min}^{L})\) to be the distance from a star leaf to \(S_{min}^{L}\)'s home and let \(L(S_{min}^{R})\) be the number of markers greater than \(S_{min}^{L}\) and on the right of \(S_{min}^{L}\). **Claim 1**. : \(T(S_{min}^{R})\) _is the minimum of \(D(S_{min}^{R})\) and \(R(S_{min}^{R})\)._  
Proof. : If \(T(S_{min}^{R})\) or \(S_{min}^{L}\) are at star leaf of \(S_{L}\) or \(S_{R}\) respectively in the current configuration of markers, we can say \(T(S_{min}^{R})=D(S_{min}^{R})\) implying \(D(S_{min}^{R})\leq R(S_{min}^{R})\). \(T(S_{min}^{R})=D(S_{min}^{R})\), where \(D(S_{min}^{L})\leq L(S_{min}^{L})\) and thus validating our claims. **Claim 2**. : \(T(S_{min}^{L})\) _is the minimum of \(D(S_{min}^{L})\) and \(L(S_{min}^{L})\)._Proof. : If \(S_{min}^{R}\) is not at a star leaf of \(S_{L}\), we can say \(R(S_{min}^{R})<D(S_{min}^{L})\). Similarly, in case of \(S_{min}^{L},L(S_{min}^{L})<D(S_{min}^{L})\), justifying the above mentioned claims. **Claim 3**. : _In algorithm \(A_{db}\), swapping Steps 1 and 2 does not alter the swap count._  
Proof. : In the initial configuration, let \(S_{L\to R}\) and \(S_{P\to R}\) to be the number of star markers residing in \(S_{L}\) and on the path, respectively, whose homes are in \(S_{R}\). Similarly, let \(S_{R\to L}\) and \(S_{P\to L}\) be the number of star markers residing in \(S_{R}\) and on the path respectively whose homes are in \(S_{L}\). Path markers can be in \(S_{L}\), \(S_{R}\), or on the path. Let the total swaps required for homing path markers be \(P=P_{P}+P_{R}+P_{L}\), where \(P_{P}\), \(P_{R}\), and let \(P_{L}\) be the swap count for homing markers residing on the path, \(S_{R}\) and \(S_{L}\) respectively. Case (1): Perform Step 1 of \(A_{db}\) followed by Step 2. Moving \(S_{min}^{R}\) towards the right, shifts the markers it encounters on the way to the left. This _shift_ decreases \(S_{R\to L}\) and \(S_{P\to L}\). Path markers entering into \(S_{L}\) (say \(P_{L}^{{}^{\prime}}\)) during a swap increase \(P\) and the number of path tokens leaving \(S_{R}\), i.e., \(P_{R}\) will result in the decrease of \(P\). \[T_{R}+(T_{L}-(S_{R\to L}+k))+(P+P_{L}^{{}^{\prime}}-P_{R}),\text{ where }0\leq k \leq S_{P\to R}. \tag{1}\]  
In Step 2, \(S_{min}^{L}\) can encounter only path markers on the way home. \(S_{min}^{L}\) shifts both \(P_{L}^{{}^{\prime}}\) markers which entered into \(S_{L}\) in Step 1 and \(P_{L}\) markers to the right.