retagged by
1,085 views
1 votes
1 votes

Merging k sorted lists of size n/k into one sorted list of n-elements using heap sort will take how much time ?

My doubt

First approach:- here it is mentioned heap sort so, heap sort will always take nlogn.and here also we have n elements and it will take nlogn.

But other method is to use heap data structure of size k and merge,it will give o(k)+(logk)*(n/k)

I think answer should be nlogn only because the second approach is not heap sort.

Please check.

retagged by

3 Answers

1 votes
1 votes

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

0 votes
0 votes

I think here only merging is asked here that means asking for time required for Bulid Heap so time required O(n/k *k)=O(n)

Related questions

1 votes
1 votes
1 answer
1
reena_kandari asked Jul 30, 2016
987 views
The number of elements that can be sorted in time using heap sort ?
1 votes
1 votes
0 answers
2
Joon asked Jul 18, 2016
526 views
Why is the space complexity of heap sort O(1) and not O(log n) even if Heap sort internally calls max_heapify whose space complexity is O(log n) due to the stack (recursi...
0 votes
0 votes
3 answers
3
nikhil1008 asked Mar 28, 2016
607 views
4) The number of elements that can be sorted in Θ(logn) time using heap sort is (A) Θ(1)(B) Θ(sqrt(logn))(C) Θ(Log n/(Log Log n))(d) Θ(Log n)