Sorting “almost sorted” array in $O(n\log\log n)$

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:

• Create an array $$B$$ of size $$\log n + 1$$.
• Go through the array $$A$$, recognize the $$\log n$$ pairs, and insert them into $$B$$.
• Sort $$B$$ using insertion sort in time $$O(\log^2 n)$$.

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$$.)

• thanks a lot for your time. – Foghunt Feb 20 at 12:00

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$$.)

• Indeed, this is simpler than my answer... – Yuval Filmus Feb 20 at 17:19