3 ms·

Would o(n+m) really be a record? I didn't see any claims on your paper about computation cost, but I have only had time to read it's summary.

• Someone 5y ago
  If, in a row of n+m items, you have to move the first one to the end and all other ones one place forward, you can, at best, move one item to its correct place per swap, except for the last swap. So, worst case, you can’t do with fewer than n+m-1 swaps. In general, to perform a permutation, you can put each of its cycles in the correct spot with one fewer swap than the number of items in the cycle. So, for a permutation with k cycles, the best you can do is n+m-k swaps.