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:

$\Theta(n)$ if $d$ is constant
$\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 &lt;- d
 for i &lt;- 1 to n 
    BUILD-MIN-HEAP(min-heap,heap-size)
      if min-heap not empty
        then EXTRACT-MIN &lt;- A[i]
          if i+d&lt;=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?
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.