We give a quadratic algorithm for finding a minimum sequence of reversals that sorts a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation of Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.
This is joint work with Ron Shamir and Bob Tarjan.