1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Apr 12 at 15:11
  • $\begingroup$ Your algorithm probably runs in time $O(n\log d)$, which satisfies your two constraints. $\endgroup$ – Yuval Filmus Apr 12 at 16:59
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.