Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given array $A$ of length $n$, we call it almost sorted if there are at most $\log n$ indices satisfying $A[i] > A[i+1]$.
Find an algorithm that sorts the array in $O(n\log\log n)$.
My attempt:
At this point I am stuck.
Suppose that $A$ is an array with $m$ indices satisfying $A[i] > A[i+1]$. You can find these indices in $O(n)$. These $m$ indices split $A$ into $m+1$ nondecreasing arrays $B_1,\ldots,B_{m+1}$ of total length $n$. We now merge them according to the following strategy: at each step, take the two shortest arrays, and merge them. You can implement the choice mechanism in $O(m\log m) = O(n\log m)$ using a heap.
When merging two arrays of length $a,b$, the running time is $O(a+b)$. Hence we would like to understand the total sum $S$ of $a+b$, where $(a,b)$ goes over all $m$ pairs of arrays being merged. To this end, we consider a merge tree, which is formed in the following way. We start with $m+1$ vertices corresponding to $B_1,\ldots,B_{m+1}$. When two arrays corresponding to vertices $x,y$ are merged, we create a new vertex with $x,y$ its only children. You can check that $$ S = \sum_{i=1}^{m+1} |B_i| \mathrm{depth}(B_i). $$ Consider now a probability distribution $X$ on $[m+1]$ with $\Pr[X=i] = |B_i|/n$. Then $S/n$ is the average codeword length of an optimal prefix code for $X$ (this is because we're essentially running Huffman's algorithm). Therefore $S/n < \log m + 1$, showing that the merging steps take $O(n\log m)$ time in total.
Summarizing, the algorithm runs in time $O(n\log m)$.
(Strictly speaking, to handle the cases $m=1$ and $m=0$, we should replace $m$ with $m+2$.)
This is a classical application of natural merge sort as described in this wikipedia entry or this algorithmist entry
What is the current case?
Let $A$ is an array with $m$ indices satisfying $A[i] > A[i+1]$. We can find these indices in $O(n)$. These $m$ indices split $A$ into $m+1$ nondecreasing arrays $B_1,\ldots,B_{m+1}$ of total length $n$. This is our start of merging processing. (Thanks to Yuval for this initial processing.)
Then we will merge $B_1$ with $B_2$ into nondecreasing array $C_1$, $B_3$ with $B_4$ into nondecreasing array $C_2$, and so on. We might have a single $B_{m+1}$ as $C_{m/2+1}$ when $m$ is even. This iteration take $O(n)$ time since merging two arrays of length $a,b$ takes $O(a+b)$ time.
Then we will merge $C_1$ with $C_2$ into nondecreasing array $D_1$, $C_3$ with $C_4$ into nondecreasing array $D_2$, and so on. We might have a single array at the end that is not merged but renamed to $D_{\text{an appropriate index}}$. This iteration take $O(n)$ time as well.
And so on.
Each iteration take $O(n)$ time. There are $\lceil \log_2(m)\rceil$ iterations. So the total time-complexity is $O(n\log m)$ for $m>1$. (The time-complexity is $O(n)$ when we find $m=0, 1$.)
