Two-dimensional homing sort

Homing sort, i.e., sorting by placement and shift, is a natural way to do hand-sorting. Elizalde and Winkler showed that (1) any n  -element permutation can be sorted by n−1n−1 or less one-dimensional homing operations; (2) no n  -element permutation admits a sequence of 2n−12n−1 or more homing operations; and (3) the number of n  -element permutations that admit a sequence of 2n−1−12n−1−1 homing operations is super-exponential in n  . In the present paper, we study sorting via two-dimensional homing operations and obtain the following observations: (1) Any m×nm×n permutation can be sorted by at most mn−1mn−1 two-dimensional homing operations. (2) If both vertical-first and horizontal-first homing operations are allowed, for any integers m⩾2m⩾2 and n⩾2n⩾2, there is an m×nm×n permutation that admits an infinite sequence of two-dimensional homing operations. (3) If only vertical-first homing operations are allowed, for any integers m⩾3m⩾3 and n⩾2n⩾2, there is an m×nm×n permutation that admits an infinite sequence of two-dimensional homing operations. (4) The number of 2×n2×n permutations that admit sequences of Ω(n2)Ω(2n) vertical-first two-dimensional homing operations is super-exponential in n  . (5) No 2×n2×n permutation admits a sequence of (2n)!(2n)! or more vertical-first two-dimensional homing operations.

► We study sorting 2-d permutations via two kinds of homing operations. ► No 2×n2×n permutation admits an infinite sequence of v-first operations. ► Some 3×23×2 permutation admits an infinite sequence of v-first operations. ► Some 2×22×2 permutation admits an infinite sequence of v-first and h-first operations.