# Does k way merge sort defies the lower bound for sorting?

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?

• $n=ck$, if $c$ is constant the asymptotic rates are the same. – lightxbulb Feb 7 at 12:29
• 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})$ – dEmigOd Feb 7 at 12:43

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.