Listing all sorting reversals in quadratic time

摘要

We describe an average-case O(n²) 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²) in the worst case.