Listing all sorting reversals in quadratic time

Abstract

Abstract We describe an average-case O(n 2) algorithm to list all reversals on a signed permutation π that, when applied to π, produce a permutation that is closer to the identity. This algorithm is optimal in the sense that, the time it takes to write the list is Ω(n 2) in the worst case.