Editorial for COCI '11 Contest 1 #5 Sort

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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$ $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)$ $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)$ $O (N \sqrt{N})$ .

Comments

0

Snapper_001 commented on Feb. 29, 2024, 11:38 a.m.

How to prove this fact that after the first pass , operation will be of subsequences of length 2 and not greater?