Sorting almost sorted array

Question

Encountered this question but I couldn't solve with the complexity they solved it:

Suppose I have an array that the first and last $\sqrt[\leftroot{-2}\uproot{2}]{n} $ elements has $\frac{n}{5}$ inverted pairs, and the middle $n - 2\sqrt[\leftroot{-2}\uproot{2}]{n}$ elemnts are sorted. What is the complexity of sorting the unsorted array?

They claim in the answer that sorting array with $I$ inversions is $O(n\log{\frac{n}{I}})$.Why?

• greybeard: Welcome to ComputerScience@SE. Please attribute quoted contents properly. (There is Markdown for block quotes: use > line prefix or "the " button" in the post editor tool-bar.) Please check the problem statement: there are just so many values of $n$ where $\frac n 5$ does not exceed 1ドル\ldots2 \times \sqrt n$.
• Albjenow: I think $I$ refers to the inversion count not to the number of swaps actually necessary to sort the array.
• Rony Kositsky: Yes, this is what I meant.
• Antti Röyskö: Is the problem statement correct? As is you could just sort the $\sqrt{n}$ long prefixes and suffices in $\mathcal{O}(\sqrt{n} \log n)$ time leading to a linear algorithm.
• Rony Kositsky: That was my answer as well, this is why I'm so confused.

Answer 1

If you have an array with a sequential range that covers all but k elements, and you know the range, then you sort the k elements in O (k log k), then merge two ranges that you know to be sorted in O (n). That sorts the whole array in O(n) as long as k is O (n / log n).

In your case k = $O (n^{1/2})$ so clearly you can sort the array in O (n).

And you don't need to know the sorted range, because for large n we have n/2 inside the sorted range, so you can just count the elements in ascending / descending order from n/2 upwards / downwards.