self doubt

Question

Consider n elements that are equally distributed in k stacks. In each stack, elements of it are arranged in ascending order (min is at the top in each of the stack and then increasing downwards). Given a queue of size n in which we have to put all n elements in increasing order. What will be the best algorithm and their time complexity?

I think Merge sort is best algorithm, O(n log logk)

 

Am I right or wrong?

 

 

Comments

I hope O(n) sufficient

---

@raj kumar
can you tell your algo..? how you are applying merge sort..?

---

@shaik how its possible in O(n).?

---

it's need only last pass of MERGE SORT but difference is we have more than 2 different arrays(stacks)

---

@shaik.

well but in last pass of merge sort you have two sorted thing here its sorted but you have k such stacks...so you need to do k-1 conparison atleast...isnt so.?

---

yes, shukla, i have made a mistake... i analyse for 3 stacks and simply assume 3 is constant...

but in question they gave k stacks... which have significant.

 

therefore time complexity = O(n.k)

---

what i think is to build min heap on k elements as k people fighting for first minimum position, delete minimum ...now u left with k-1 elements so insert one more as every time k people fight..so total should be nlogk...correct me if i am wrong..?

---

@shaik

O(n) is not possible i am sure

---

@shubham Shukla

It is similar problem like merge the k sorted list each list contain m element.

in this case, time complexity is O(mk.log k).

In the similar fashion, I think here.

I hope you got it.

---

@raj kumar

ok...than n loglogk would be best..

---

what will be final answer here ??. I think $O(nlogk)$??

---

@srestha i think merge sort gives better answer here i.e nloglogk  but only if space is not problem.

otheriwse nlogk

here they have already given queue of size n so i think this limit our space...is not so srestha..?

if need to improve time than space increases basic funda..... so best algo i think would be taking O(nloglogk)