The Gateway to Computer Science Excellence
0 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.

in Algorithms by Boss (25.5k points)
edited by | 235 views
What is head data structure??
It was a typo!!
By second approach will it not be O(nlogk)????
Yes.I mentioned in question itself:)

2 Answers

0 votes
Nlogk will be ans
by (299 points)
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)

by (61 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,245 answers
104,614 users