size of each list is n/k and there are k such list
cost of sorting
->with the heap sort cost of sorting each list is n/k*log(n/k) for one list
->for k lists it is k*n/k*log(n/k)=n*log(n/k) =0(n*logn)
cost of merging k lists
->n/k n/k n/k n/k n/k …..n/k such k lists are there
2n/k 2n/k 2n/k…..2n/k such k/2 lists
4n/k 4n/k ….4n/k such k/4 lists
.
.
.
2$^{i}$n/k=n
2$^{i}$*1/k=1
i=log$_{2}^{K}$ that is height
and at each level cost of merging is 0(n)
Total cost of merging=n*log$_{2}^{K}$
Total cost=Heapsort cost + merging cost
0(nlogn+nlogk)=nlogn