Circular sorting

2025/02/20 by Adin, Ron M., Alon, Noga, Roichman, Yuval · 1 citation
#05A05 #68P10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2502.14398

Abstract

We determine the maximal number of steps required to sort n labeled points on a circle by adjacent swaps. Lower bounds for sorting by all swaps, not necessarily adjacent, are given as well.

Cited by

• CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)

Related

• Circular sorting, strong complete mappings and wreath product constructions
• An Upper Bound on the Number of Circular Transpositions to Sort a Permutation
• An In-Place Sorting with O(n log n) Comparisons and O(n) Moves
• Sorting as Gradient Flow on the Permutohedron
• Sorting by Placement and Shift