# Sorting almost sorted array

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?

• 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$. Feb 10, 2020 at 8:00
• I think $I$ refers to the inversion count not to the number of swaps actually necessary to sort the array. Feb 10, 2020 at 8:04
• Yes, this is what I meant. Feb 10, 2020 at 8:13
• 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. Feb 10, 2020 at 9:10
• That was my answer as well, this is why I'm so confused. Feb 10, 2020 at 9:14

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