Support there is a Array A with size n and let n be a multiple of k. If we divide the A into sub arrays each with elements k and sort them individually, it would require k*log(k) time. Total initial time =(n/k)klog(k)=nlog(k). And then merging the sorted sub arrays, let say using a heap of size k will cost atmost nlog(k) time. So total time = 2*nlog(k)+c which is O(nlog(k)). But we know that lower bound for sorting is n*log(n). What is wrong in my thinking?

  • $\begingroup$ $n=ck$, if $c$ is constant the asymptotic rates are the same. $\endgroup$
    – lightxbulb
    Feb 7 '19 at 12:29
  • $\begingroup$ I think you are mistaken, that merging could be done that fast. You have $\frac{n}{k}$ sorted arrays of size $k$ , so I do not see a way to merge them faster than $O(n log \frac{n}{k})$ $\endgroup$
    – dEmigOd
    Feb 7 '19 at 12:43

The problem comes from merging the arrays.

What I think you're thinking when using a heap is to keep track of the smallest elements from each of the $k$-element sorted arrays, removing the smallest element $s$ them from the heap, putting $s$ in the output, and adding a new element onto the heap from the array which contained $s$.

The problem with this is that there are $n/k$ arrays, so your heap will actually contain $n/k$ elements.

As an extreme case, let $k=1$. Then your algorithm would consist of sorting each 1-element array (which takes no time) and then merging them using heapsort.


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.