Publication
Polynomial Block Lengths Are Necessary and Sufficient to Beat Insertion Sort
ECCC TR26-256, 2026. PDF · Official record
Abstract
Insertion sort is a basic algorithm for sorting permutations: it repeatedly cuts out one element and inserts it at its place among the elements sorted so far. It sorts every permutation of length \(n\) with at most \(n-1\) such moves, and some permutations cannot be sorted with fewer moves (Heath and Vergara, 1998). A move that cuts out a block of any length is called a transposition, and the number of transpositions that suffices to sort every permutation lies between \(n/2\) and \(2n/3\) for \(n \ge 9\) (Bafna and Pevzner, 1998; Eriksson, Eriksson, Karlander, Svensson, and Wästlund, 2001). We ask how long the cut blocks must be to beat insertion sort by a constant factor.
We show that cut blocks of polynomial length are necessary and sufficient. If the cut blocks have length \(n^{o(1)}\), then some permutations need \(n-o(n)\) moves, whereas for any \(\alpha>0\), \((1-\varepsilon_\alpha)n\) moves with cut blocks of length \(n^\alpha\) suffice for all large enough \(n\). The lower bound follows from a new upper bound on the number of permutations at a given distance from the identity. The upper bound follows from a recursive reduction of the exponent, starting from the known bound for unrestricted transpositions.