Quantifying CDS Sortability of Permutations Using Strategic Piles

We investigate the sorting of permutations using context directed swaps (CDS). Sorting has important applications in mathematics and other disciplines, such as biology and computer science. Not all permutations are CDS sortable. We seek to quantify the degree of sortability. Prior work introduced the concept of fixed points, which represent permutations on which no more swaps can be made. We develop mathematical methods for quantifying the number of permutations from which a given number of fixed points can be reached. These methods incorporate fields such as combinatorics, algebra, and graph theory. We also consider this problem from a game theoretic perspective by exploring strategic methods for reaching specific fixed points. Our findings include formulas that explain both previously reported and newly collected data. These results clarify the role of CDS as a sorting operation.