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$
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$
  • $\begingroup$ thanks a lot for your time. $\endgroup$ – Foghunt Feb 20 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
    $\begingroup$ Indeed, this is simpler than my answer... $\endgroup$ – Yuval Filmus Feb 20 at 17:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.