# 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.
Commented Feb 9, 2019 at 18:05

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? Commented Feb 10, 2019 at 3:03
• Right, all the big O’s should be $\Omega$. Commented Feb 10, 2019 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.
– user35837
Commented Feb 10, 2019 at 5:47
• I don’t understand your question. What smaller number did you put? Commented Feb 10, 2019 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.
– user35837
Commented Feb 10, 2019 at 6:06