Iterate once with each other worst algo, compare the lists, consider matching moved locations to be sorted and choose that as the input for the next iteration.

Wouldn't that necessarily be slower than all other algos, and also demonstrably be sorting, and - if each other algo's termination is bounded - have a bounded termination time.

It might not terminate for all lists, in theory; you could have a watchdog to cure that I think.