In the merge sort algorithm, when merging two sorted lists of sizes m and n, the worst-case number of comparisons is given by:
m+n−1
Explanation:
- The merge operation compares elements from both lists to build a single sorted list.
- In the worst case, every comparison places one element into the merged list until one of the two lists is empty.
- Once one list is exhausted, the remaining elements from the other list are directly appended without further comparisons.
So, the worst-case number of comparisons required is m+n−1
Example :
List 1: [4,10,13]
List 2: [5,7,11]
Process:
Compare 4 and 5: 4 is smaller, so add 4 to the merged list.
Merged List: [4], Remaining: [10,13] and [5,7,11]
Compare 10 and 5: 5 is smaller, so add 5 to the merged list.
Merged List: [4,5] Remaining: [10,13] and [7,11]
Compare 10 and 7 : 7 is smaller, so add 7 to the merged list.
Merged List: [4,5,7]Remaining: [10,13] and [11]
Compare 10 and 11: 10 is smaller, so add 10 to the merged list.
Merged List: [4,5,7,10] Remaining: [13] and [11]
Compare 13 and 11: 11 is smaller, so add 11 to the merged list.
Merged List: [4,5,7,10,11] Remaining: [13] and [ ]
Add the remaining 13 to the merged list (no comparison needed).
Merged List: [4,5,7,10,11,13]
Total Comparisons:
- 4 vs 5
- 10 vs 5
- 10 vs 7
- 10 vs 11
- 13 vs 11
Total = 5 comparisons
This matches m+n−1= 3+3−1= 5
