Sorted List

Question

suppose there are 4 sorted lists of n/4 elements each. if we merge these list into a single sorted list of n elements, for the n=400 number of key comparisons in the worst case using an efficient algorithm is

Comments

Change title of question with appropriate one like algorithm

Answer 1

There are 4 sorted list each of size 100, as n=400
f1 = 100 records
f2 = 100 records
f3 = 100 records
f4 = 100 records

Combining f1 and f2 needs 100 + 100 - 1 = 199 comparisons, in worst case.
Combining f3 and f4 needs 100 + 100 - 1 = 199 comparisons, in worst case.

 Now we have two sorted & merged files each of size 200, hence we need 200 + 200 -1 = 399 comparisons to merge these files into one file of size 400.

hence total comparisons are required : 2*199 + 399 = 398 + 399 = 797

Note that using MERGE procedure, if there are two files, one with m records, and second with n records, need m+n-1 comparisons in worst case.

Comments

What if we merge f1 and f2 first (and call it f12) this gives 199 comparisons then merge f12 with f3 and (call it f123) this gives another 299 comparisons

And finally merge f123 with f4 this gives 399 comparisons. So total comparisons are 897

What is wrong with this approach?

---

Yeah someone please answer @Gaurangi Katiyar

---

You are not using an efficient algorithm. For Total comparison=797 it uses 2 way merging which is efficient here.

Answer 2

Combining 1 and 2 needs 100 - 1 = 99 comparisons  in worst case.
Combining 3 and 4 needs 100 - 1 = 99 comparisons  in worst case.

 So we have two sorted  merged files each of size 200, so we need 200  -1 = 199 comparisons to merge

 total comparisons : 2*99 + 199 = 397

Using merge function.

Comments

Let us say two lists are 1,2,3 and 4,5,6.When we are combining we compare 1 with 4 as 1<4 we write 1 in combined list.Similarly 2 and 4 and then 3 and 4.So total of n comparisons in worst case.But why are u considering n-1 comparisons???

Answer 3

Check this out:   https://stackoverflow.com/questions/8535540/exactly-how-many-comparisons-does-merge-sort-make