Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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:
The array can be sorted in $O(n\log\log n)$.
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.
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)$.
