  In 1937, biologists Sturtevant and Tan posed a computational question:
transform a chromosome represented by a permutation of genes, into a second
permutation, using a minimum-length sequence of reversals, each inverting the
order of a contiguous subset of elements. Solutions to this problem, applied to
Drosophila chromosomes, were computed by hand. The first algorithmic result was
a heuristic that was published in 1982. In the 1990s a more biologically
relevant version of the problem, where the elements have signs that are also
inverted by a reversal, finally received serious attention by the computer
science community. This effort eventually resulted in the first polynomial time
algorithm for Signed Sorting by Reversals. Since then, a dozen more articles
have been dedicated to simplifying the theory and developing algorithms with
improved running times. The current best algorithm, which runs in $O(n \log^2 n
/ \log\log n)$ time, fails to meet what some consider to be the likely lower
bound of $O(n \log n)$. In this article, we present the first algorithm that
runs in $O(n \log n)$ time in the worst case. The algorithm is fairly simple to
implement, and the running time hides very low constants.
