In this part, you will look at some further examples of how Strategy $2$ performs compared to Strategy $1.$

i$.$Merging two lists of length m and n respectively never needs more than m $+$ n $1$ comparisons.

This is because each comparison results in an item being moved to the merged list. If there are m $+$ n items altogether then if we ever got to m $+$ n $1$ comparisons it would mean we had moved all but one of the items to the merged list and the final item could be moved without any comparison.

This is the worst case; in general we are likely to need fewer than m $+$ n $1$ comparisons.

Suppose the first list contained $18$ items and the second list contained $5$ items.

How many comparisons would Strategy $1$ take to sort a combined list of $23$ items?

Considering Strategy $2,$ what is the greatest number of comparisons it could take to bubble sort the first and second lists individually, then merge the results?

Comment briefly on the difference in performance.

ii$.$Is Strategy $2$ always an improvement on Strategy $1?$ Consider an extreme case. Suppose the first list has only $1$ item and the second list has $18$ items. Following the same method as in part $($i$)$ above, calculate the maximum number of comparisons required by each strategy and comment briefly on what you find.