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)$.
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.