The bound $m+n-1$ is achieved by a linear merge: Start with a pointer at the beginning of each list, compare the two elements pointed to, add the smaller one to the merged list and increase that pointer. In case you have to compare the last two elements, you've made $(m-1)+(n-1)$ comparisons to get to that point, so the worst case takes $m+n-1$ operations.
[Edit in response to the edit in the question:]
For simplicity, let's assume that all values are different so that all comparisons have a binary result. (Since this is about worst-case behaviour, we can make arbitrary assumptions about the input.) With $k$ binary results, you can distinguish at most $2^k$ different cases. The result of merging two sorted lists of lengths $m$ and $n$ can be specified by the positions of the $m$ elements of the one list in the merged list, and there are $\binom{m+n}m$ different arrangements of these positions. Thus you need at least $\left\lceil\log_2\binom{m+n}m\right\rceil$ comparisons. That solves cases c) and d), since
$$\left\lceil\log_2\binom{3+4}3\right\rceil=\left\lceil\log_235\right\rceil=6=3+4-1$$
and
$$\left\lceil\log_2\binom{4+4}4\right\rceil=\left\lceil\log_270\right\rceil=7=4+4-1\;.$$
Case b) needs a bit more work, since
$$\left\lceil\log_2\binom{2+4}2\right\rceil=\left\lceil\log_215\right\rceil=4\lt2+4-1\;.$$
To allow the merge to be done with $4$ comparisons, the first comparison would have to divide the $15$ possibilities into two groups of $8$ and $7$; otherwise one of the groups would have more than $8$ possibilities and couldn't be resolved with the remaining $3$ comparisons. Due to the symmetry between greater and lesser, we only have to consider comparisons involving the first element of the two-element list as first comparisons. Comparing the first element of the two-element list with one of the four elements of the other list divides the $15$ possibilities into groups of $10/5$, $6/9$, $3/12$ and $1/14$, respectively. Since there's a group with more than $8$ elements in each case, it's impossible to do the merge with $4$ comparisons in all cases.
Consider the set $z_{i,j} = \{z_i,z_{i+1},....,z_{j-1},z_j\}$ This set order is in terms of the values (not the order in the Array) i.e. $z_i<z_j \;and\; j>i$. As long as none of the these are chosen as pivot,all are passed to the same recursive call.
i.e. pivot $\leftarrow$ x
$x > z_{j} or \; x<z_{i}$ , $z_{i,j}$ is passed to same recursive call.
Consider the case when either of $z_{i},...z_{j} $ gets chosen as pivot.
a) if $z_i$ or $z_j$ gets chosen first, then $z_i$ and $z_j$ get compared.
b) if one of the $z_{i+1} ... z_{j-1}$ gets chosen first,then $z_i$ and $z_j$ are never compared.
$Pr\{z_i z_j compared\} = Pr\{X=z_i\} + Pr\{X=z_j\}$
PS: $Pr\{X=z_i\} = Pr\{X=z_j\} = 1/(j-i+1)$
I hope it helps.
Best Answer
Reading through the slides I noticed the insertion sort implementation discussed here is actually sub-optimal: An element is swapped into place in a bubble-sort like manner. Since the sorted list at step $i$ has $i$ elements, the average number of comparisons (= swaps - 1) needed to sort the $i+1$-st element into place is $$\frac12(1_{\text{element is in place}} + i_{\text{element is smallest yet}})$$ So actually the correct average case estimate would be $$\sum_{i=1}^{N-1} \frac{i+1}2 = \frac{(N-1)N}4 + \frac{N-1}2 = \frac{(N-1)(N+2)}{4}$$ But this is also $\mathcal O(n^2)$ so that's a minor mistake.