# Optimal Algorithms for Sorting Permutations with Brooms
## 4 Sorting Permutations with a Double Broom
### Correctness of \(A_{db}\)
Observe that \(n\) can be placed on center in exactly \(d-1\) swaps, where \(d\) is the distance of \(n\) from its home vertex \(H_{n}\) on the star leaf. Let \(S_{c}\) be the swap in \(S^{\prime}=S_{1},S_{2},\ldots,S_{c}\) that places marker \(n\) on the center and \(T\) be the intermediate configuration of the markers after \(S_{c}\). Create a swap sequence S that homes \(n\) first in \(d-1\) swaps and carries out the rest of the \(c-(k-1)\) swaps which does not include \(n\). Clearly, you will get the same resulting configuration as of \(T\) with the same number of swaps. Hence, \(S\) is an optimal swap sequence. Now, call \(S_{h}\) the swap that homes \(n\) from the center vertex of \(S_{R}\) by swapping it with an arbitrary marker \(t\) residing on \(H_{n}\). Previous discussion assumes that no swaps occur on the star edges before \(S_{h}\). Otherwise, when n is initially placed on the center vertex or arrives at the center with the swap \(S_{c}\) it suffices to show that \(S_{opt}\) is optimal and does not alter the position of \(n\) before the swap \(S_{h}\). We do some modifications in \(S_{opt}\) to make this true. Split the subsequence \(S_{1},S_{2},\ldots,S_{h-1}\) into two subsequences \(S_{path}\) and \(S_{star}\). \(S_{path}\) contains the swaps that occurs on path edges and \(S_{star}\) contains the swaps that occurs on star edges. Note that \(S_{path}\) does not move marker \(n\) from its position and \(S_{star}\) always places \(n\) back to the center. We can rearrange this subsequence containing \(S_{star}\) and \(S_{path}\) as no star markers move towards the path and vice versa, due to the aforementioned Property 5. After \(S_{path}\), carry out the swap \(S_{h}\) and then perform the swaps in \(S_{star}\) but with \(t\) in place of \(n\). Note that we can use the same argument for \(n\) placed on \(S_{L}\) and prove the optimality of the subsequence as in Case 1. Clearly, this gives the same placement of markers with same swap count on the star and path. Hence, \(S_{opt}\) is optimal and is same as the sequence generated by our algorithm \(A_{db}\). Case (3): Assume \(n=S_{min}^{R}\) is on the leaf vertex of \(S_{L}\). Let \(t\) be the marker on the center vertex and \(S_{h}\) be the swap involving \(n\) and \(t\). If there are no swaps before \(S_{h}\), then just perform \(S_{h}\) and use the argument from Case 2 to prove the optimality of the sequence \(P_{opt}\). Otherwise, suppose there exists a cyclic permutation \(P_{s}\) of length \(L_{s}-1\) for the markers residing in \(S_{L}\). Cycles which do not include \(n\) are not taken into consideration, as solving those cycles will not alter the position of \(n\). Similar to the argument used for star, we prove that the \(P_{s}\) can be solved in \(L_{s}\) swaps. Each marker in \(C\) is far away by two swaps from its home, so the total distance is \(2(L_{s}-1)\). However, as one swap helps us move two markers near to their respective homes, our requirement is only \(L_{s}-1\) swaps. Interestingly, the initial and the final swap of \(P_{s}\) moves only one marker which belongs to \(P_{s}\). Adding the swap of \(n\) and \(t\) results in a total of \(L_{s}+1\) swaps contradictory to \(L_{s}-1\) swaps to sort \(P_{s}\).