Comparisons for merging four arrays

Question

Suppose there are 4 sorted lists of 8 elements each. If we merge these lists into a single sorted list of 32 elements. The key comparisons that are needed in the worst case using an efficient algorithm are ____.

Comments

Good read: https://xlinux.nist.gov/dads/HTML/optimalMerge.html

---

Similar question and excellent answer : https://gateoverflow.in/1997/gate2014-2-38?show=1997#q1997

---

https://gateoverflow.in/154664/optimal-merge

Answer 1

Answer 2

Answer 3

I got answer as 48.

my logic-

there are 4 lists with 8 sorted elements.

lets pick all the first four and compare them to find smallest. that would be 3 comparisons.

to find the 2nd smallest it would require 2 comparisons and 1 comparison to find 3rd smallest.

therefore 3+2+1=6 comparisons in total.

if we do this 8 times we will get 6*8=48

what's the flaw in this logic?

Nevermind  i know now why it's wrong

Answer 4

Solution.