# Optimal Algorithms for Sorting Permutations with Brooms
## 4 Sorting Permutations with a Double Broom
### Correctness of \(A_{db}\)  
In this section, we prove that our algorithm \(A_{db}\) generates an optimal swap sequence on a double broom. Initially, we discuss some properties required to prove the correctness of our algorithm. Section 1 covers the proof for properties 1 to 5. 1. Two same markers will not swap more than once;
2. Star markers belonging to the respective star enter into the star in the increasing order of their distances from that star;
3. Star markers belonging to the respective star never swap with each other on the path edges. Note that the star marker belonging to \(S_{L}\) treats the edges of the \(S_{R}\) as path edges and vice-versa;
4. Swaps on the stem involving at least one stem marker--the larger of the markers will move to the right'
5. No star marker residing on one if its star vertices moves past the first path edge;
6. In a swap \(s=(l,r)\) where \(l\in S_{L}\) and \(r\in S_{R}\), \(l\) always moves to the left and \(r\) to the right. Proof. : We prove it by contradiction. A _badswap_ involves moving \(l\) to the right and \(r\) to the left. Suppose \(S\) has a _badswap_ on the path. We show how \(S\) can be modified to obtain a new swap sequence which contains fewer swaps on the path. Property 1 restricts us from directly swapping them again. Therefore, marker \(r\) will move to the star leaf of \(S_{L}\)(or \(l\) will move to the star leaf of \(S_{R}\)), then marker \(l\) to another star leaf of \(S_{L}\) (or \(r\) will move to another star leaf of \(S_{R}\)) and then \(l\) goes to the center of \(S_{l}\) (or \(r\) will move to the center of \(S_{R}\)). Let us call this intermediate placement of markers \(S^{\prime}\). To modify \(S\), omit the swap of \(l\) and \(r\), and carry on with the preceding swaps with \(l\) and \(r\) exchanged until the state \(S^{\prime}\) is reached. This results in the same swap count, though a swap on star replaces a swap on path. Theorem 4.2: _Algorithm \(A_{db}\) generates an optimal swap sequence, i.e., a sorting sequence with the least possible number of swaps._  
Proof. : We prove that our algorithm obtains an optimal swap sequence by applying induction on marker \(n\). For the base case, the double broom has no path edges and it is only a star (either \(S_{R}\) or \(S_{L}\)). It is interesting to note that, this algorithm \(A_{db}\) is equivalent to writing:  
1. While \(\exists\) a \(S_{min}^{R}\) marker, home \(S_{min}^{R}\). 2. Run \(A_{db}\)
3. Solve \(S_{R}\)  
As discussed in the previous section, \(A_{b}\) obtains an optimal solution and we are now left to prove only in case of \(S_{min}^{R}\). Depending on the position of \(S_{min}^{R}\), we consider different cases and prove them individually. In the general induction step, we prove that swaps performed by \(S_{min}^{R}\) are part of the optimal swap sequence. Case (1): Assume marker \(n=S_{min}^{R}\) is initially placed on a stem vertex, except the center node of \(S_{R}\). Let \(P_{opt}^{\prime}\) be the optimal swap sequence. Property 2 and Property 3 ensuresthat n will never swap with a star marker on its way home in \(S_{R}\). Let \(d\) be the distance from the position of marker \(n\) to its home \(H_{n}\). So, there are exactly \(d\) swaps in \(P_{opt}^{\prime}\) which contain marker \(n\). Let \(S_{i}\) be the swap that homes marker \(n\), therefore \(S_{1}\), \(S_{2},\ldots,S_{i}\) contain \(d\) swaps which includes marker \(n\) and \((i-d)\) swaps that do not include marker \(n\). Let this intermediate configuration be \(T\). Create a separate swap sequence \(P_{opt}\) which takes the initial \(d\) swaps to homes \(n\), followed by \(i-d\) swaps that do not involve \(n\) and then carry on with rest of the swaps from \(S_{i+1},\ldots,S_{k}\). Initial \(d\) swaps leave the remaining markers in the same relative order. We have attained the same configuration state as in T implying the swap sequence \(P_{opt}\) is optimal and is same as the one generated by our algorithm \(A_{db}\). Case (2): Consider \(S^{\prime}\) be an optimal swap sequence which brings \(n\) to the center vertex.