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

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.

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.