Think of an in-place version of the insertion-sort algorithm that, after an linear-time preprocessing step, only swaps elements that are inverted.