Let us first show that the sorting algorithm is correct. Consider the leftmost smallest element in the sequence. Until it is in the first position, every pass of the algorithm will apply a reverse operation on a subsequence including that element, thus moving it towards the beginning of the sequence. Once it is in the first position, it can be ignored. The procedure continues on the remainder of the sequence until each element is in the correct position.

Notice that, after the first pass, all reverse operations will be applied to subsequences with length ~2~. Since every element will, in some step, exchange positions with every greater element in a smaller position and every smaller element in a greater position, we are left with a classical problem of computing the number of inversions in a sequence.

A Fenwick tree can be used to solve the problem with complexity ~\mathcal O(N \log N)~. It is also possible to solve the problem using an interval (tournament) tree or merge sort, with the same complexity, or a bucket-based algorithm with complexity ~\mathcal O(N \sqrt N)~.