Sorting signed permutations by reversals using link-cut trees

Seeking an O(nlog⁡n) algorithm requires to drop the b addend in the running time formulas, which prevents the choice of a large b. To this end, we propose an implementation of the algorithm whose originality lies in the use of O(log⁡n) aggregate operations allowed by link-cut trees, and by their filiform variant called log-lists. The resulting algorithm has the advantage of reaching a running time of O(n(nblog⁡b)), but also has the drawback of potentially making use of very large numbers, reducing in practice the choices of b.