# Sorting lower bounds for almost sorted array

Can't find a good way to tackle the problem. Would appreciate any help.

$$A$$ is an $$n$$ items array from an ordered set, in which every item is at most $$\log n$$ indices away from its position in the sorted array.

Show that:

1. The array can be sorted in $$O(n\log\log n)$$.

2. There is a lower bound of $$\Omega(n\log\log n)$$ for sorting $$A$$ using comparisons.

The general idea is more important than details for both assertions.

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Feb 9 at 18:05

## 1 Answer

Suppose that every element is at most $$k$$ elements away from its true position. In order to sort the array, you maintain a heap. At step $$i$$, you add $$A_i$$ to the heap, and pop the minimum element as $$A_{i-k}$$. You do no popping in the first $$k$$ steps, and no adding in the last $$k$$ steps; there are $$n+k$$ steps in total. Since the heap is always of size $$k+1$$, this runs in time $$O(n\log k)$$.

To see that this works, note that the first element in the sorted array must be one of the first $$k+1$$ elements, and in particular it must be the minimum of these elements. The second element could be any of the remaining elements or the $$(k+2)$$'th element, and in particular it must be the minimum of these elements. And so on.

For the lower bound, partition $$n$$ into blocks of length $$k$$, and consider the set of all permutation which fix each block. The number of such permutations is $$k!^{n/k} = [\Omega(k)^k]^{n/k} = \Omega(k)^n.$$ Hence the number of comparisons is at least $$\log [\Omega(k)^n] = \Omega(n\log k)$$.

• So where is the typo? – Yuval Filmus Feb 10 at 3:03
• Right, all the big O’s should be $\Omega$. – Yuval Filmus Feb 10 at 4:13
• I have understood the lower bound, but I have one question. Is $k!$ tight? To me, it appears that I put a smaller number than $k!$. I know it will not matter in the analysis but just in a case. – aaag Feb 10 at 5:47
• I don’t understand your question. What smaller number did you put? – Yuval Filmus Feb 10 at 5:53
• @ Yuval Filmus In the first block there is going to be $k!$ many but in the second it has to be less as each element is at a distance $k$ from its sorted position. I may not have understood the proof. – aaag Feb 10 at 6:06