doubt

Question

Given 8 sorted lists, each list of size n/8. If we merge these lists into a single sorted list of n elements, how many comparisons are required in worst case using an efficient algorithm?

How to do this..pls help..

Comments

Shouldn't it be n.log n using merge sort?

---

Is it 2 way merge? log 8 * n elements =3n.

Answer 1

Each pass requires 8(n/8) comparisons i.e. n. A nd the height of the tree is 8. So total time n*log8 i.e (3n)

Answer 2

total comparisons will be 3n-7 as each time it compaares total-1 max.

so for first time it will form 4 arrays of n/4 total comparissons to reach this is 4*n/4 - 4 for each same for second level 2*n/2-2 n final level n-1 so total is 3n-7