4
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ thanks a lot for your time. $\endgroup$
    – user99038
    Feb 20, 2019 at 12:00
3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Indeed, this is simpler than my answer... $\endgroup$ Feb 20, 2019 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy