# Sort a $d$-sorted array

An array is $$d$$-sorted if every key in the array is located at a distance at most $$d$$ from its location in the sorted array.

I need to write an algorithm that get a $$d$$-sorted array of length $$n$$ and sort it in the following running times:

1. $$\Theta(n)$$ if $$d$$ is constant
2. $$\Theta(n\log\log n)$$ if $$d = \Theta(\log n)$$.

My attempt:

I wrote the following pseudo-code:

Sort_d_array(A[],d)
min-heap-size <- d
for i <- 1 to n
BUILD-MIN-HEAP(min-heap,heap-size)
if min-heap not empty
then EXTRACT-MIN <- A[i]
if i+d<=n
then heap-insert-min(min-heap,A[i+d])


But in terms of runtime, all I get is $$O(n\log\log d)$$.

My method: I initialize $$i \gets 1$$ and then I build a min-heap that contains the first $$d$$ elements.

As long as the heap is not empty, I use EXTRACT-MIN and put the element at index $$i$$ in the array. If $$i+d \le n$$, then I add the element at index $$i+d$$ to the min-heap.

Any help?

• An algorithm with running time $O(n \log \log d)$ would allow to sort $n$ elements in time $O(n \log \log n)$ (just pick $d=n$). Since your algorithm is comparison based, this contradicts the lower bound of $\Omega(n \log n)$ on the running time of any comparison-based sorting algorithm. Apr 12, 2021 at 15:11
• Your algorithm probably runs in time $O(n\log d)$, which satisfies your two constraints. Apr 12, 2021 at 16:59

Since your heap contains $$d$$ elements, every operation takes take $$O(\log d)$$, for a total running time of $$O(n\log d)$$.
When $$d$$ is constant, this is $$O(n)$$, and when $$d = O(\log n)$$, this is $$O(n\log\log n)$$.
For a matching $$\Omega(n\log d)$$ lower bound, see this question.