Sort a $d$-sorted array

Question

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?

Answer 1

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.