MadeEasy Subject Test 2019: Algorithms - Sorting

Question

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

Comments

Yes it can be 31+31 +63 which is 125

But @Magma if we use optimal merge patterns can't we do as below

16  16--> 31

16  32--> 47

16  48--> 63

total 141??

---

but @Hemanth_13 the question says using an efficient algo so shouldnt it be 125? ie : 31+31+63

---

Sorry I  have applied the algorithm in the wrong way..:)

Answer 1

We have to sort 4 lists of size 16 each in a single list using an efficient algo. Here efficient algo means that we should have minimum comparisons.. Now for that we select lists of minimum size and then merge them So first we merge 2 16 sized lists with each other.

In merging the comparisons required in this case(worst case) are 16+16-1(i.e generalization=m+n-1 where m and n are the size of the lists to be sorted )=31.

We merge the other 2 16 sized lists=31 comparisons.

Now we merge the 2 32 sized lists , so no of comparisons are=32+32-1=63

Total no of comparisons are=31+31+63=125 Ans

Answer 2

Consider the following tree:

Count the internal nodes = 31+31+63 = 125

Comments

Hi @srestha why are we not merging 16+ 16 = 32 theb 32+16=48 then 48 +16 = 64 that gives 31+47+63 = 141 comparison in worst case

Answer 3

(16+16-1)+(16+16-1) COMPARISIONS IN 1ST PASS OF MERGE ALGO

(32+32-1)  IN  LAST PASS

SO TOTAL 31+31+63=125 ........I THINK

Answer 4

There are 4 sorted list each of size 100, as n=400
List 1 = 100 records
List 2 = 100 records
List 3 = 100 records
List 4 = 100 records

Combining L1 and L2 needs 16 + 16 - 1 = 31 comparisons, in the worst case.
Combining L3 and L4 needs 16 + 16 - 1 = 31 comparisons, in worst case.

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

hence total comparisons are required : 2*31 + 63 = 125

Important point: In case of MERGE procedure, if there are two files, one with m records, and second with n records, then we need m+n-1 comparisons in the worst case.

Comments

Why -1 ?

---

Shamim for merge sort procedure we take m+n-1 comparisons.

Try taking small arrays and do the merge comparisons.

You will get more clarity.

In short, in merge procedure the number of comparisons made are m+n-1.

---

That's the mistake i made.. I got the answer 128 :). Thank you buudy.. I appreciate your efforts.

---

Thanks.