Circular sorting

Ron M. Adin, Noga Alon, Yuval Roichman

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 giv…