Back to the 2022 paper

Module 1: Introduction

20222m

The average number of comparisons performed by merge sort algorithm in merging two sorted lists of 2 elements is
(i) 8/5
(ii) 11/7
(iii) 11/6
(iv) 8/3

Worked SolutionAI Assisted

Answer: (iv) 8/3≈2.678/3 \approx 2.67

Explanation:

Merge of two sorted lists A=[a1<a2]A=[a_1<a_2], B=[b1<b2]B=[b_1<b_2] with all 4! / (2!2!) = 6 interleavings equally likely (distinct elements, random order). Standard merge:

 i=j=0, comps=0
 while i<2 and j<2: comps++; if A[i]<B[j] i++ else j++

Best case = 2 comps (one list entirely smaller: a1<a2<b1<b2a_1<a_2<b_1<b_2 or b1<b2<a1<a2b_1<b_2<a_1<a_2)
Worst case = 3 comps (interleaved).

Enumerate:

  1. a1<a2<b1<b2a_1<a_2<b_1<b_2: a1 ⁣< ⁣b1a_1\!<\!b_1, a2 ⁣< ⁣b1a_2\!<\!b_1 → 2
  2. a1<b1<a2<b2a_1<b_1<a_2<b_2: a1 ⁣< ⁣b1a_1\!<\!b_1, b1 ⁣< ⁣a2b_1\!<\!a_2, a2 ⁣< ⁣b2a_2\!<\!b_2 → 3
  3. a1<b1<b2<a2a_1<b_1<b_2<a_2: a1 ⁣< ⁣b1a_1\!<\!b_1, b1 ⁣< ⁣a2b_1\!<\!a_2, b2 ⁣< ⁣a2b_2\!<\!a_2 → 3
  4. b1<b2<a1<a2b_1<b_2<a_1<a_2: 2 (symmetric to 1)
  5. b1<a1<b2<a2b_1<a_1<b_2<a_2: 3
  6. b1<a1<a2<b2b_1<a_1<a_2<b_2: 3

Average = (2+3+3+2+3+3)/6=16/6=8/3(2+3+3+2+3+3)/6 = 16/6 = 8/3.

Worst-case merging m+n−1=3m+n-1 =3, best min⁡(m,n)=2\min(m,n)=2, average 8/38/3.

Correct choice: (iv) 8/38/3

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.