Complexity of Merge Sort that splits in a random position
For definiteness, let us suppose that the $T(1) = 1$ and that if the split is $k+(n-k)$ then the running time is $T(k) + T(n-k) + n$.
The recursion for the worst-case running time is therefore
$$
T(n) = \begin{cases} \max_{1 \leq k \leq n-1} T(k) + T(n-k) + n &amp; \text{if } n &gt; 1 \\ 1 &amp; \text{if } n = 1. \end{cases}
$$

In order to calculate the worst-case complexity, we need both an upper bound and a lower bound. You already gave the lower bound:
$$
T(n) \geq T(1) + T(n-1) + n = T(n-1) + n+1.
$$
Iterating this easily yields $T(n) = \Omega(n^2)$.

In the other direction, let us prove that $T(n) \leq n^2$ for all $n$. The base case is clear. For the inductive case,
$$
T(k) + T(n-k) + n \leq k^2 + (n-k)^2 + n \leq 1 + (n-1)^2 + n = n^2 - n + 2 \leq n^2,
$$
since $n \geq 2$. It follows that $T(n) = \Theta(n^2)$.

(In fact, with some more work you should be able to show that $k=1$ is indeed (together with $k=n-1$) the worst choice.)

Let us now proceed to the average case running time (i.e., the expected running time), which satisfies the recurrence
$$
S(n) = \begin{cases} \frac{1}{n-1}\sum_{1 \leq k \leq n-1} [S(k) + S(n-k)] + n &amp; \text{if } n &gt; 1 \\ 1 &amp; \text{if } n = 1. \end{cases}
$$
We can simplify the inductive case to
$$
S(n) = \frac{2}{n-1} \sum_{1 \leq k \leq n-1} S(k) + n.
$$
This implies that for $n \geq 2$,
$$
n S(n+1) = 2(S(1) + \cdots + S(n)) + (n+1)n, \\
(n-1) S(n) = 2(S(1) + \cdots + S(n-1)) + n(n-1).
$$
Subtracting gives
$$
nS(n+1) - (n-1)S(n) = 2S(n) + 2n \Longrightarrow nS(n+1) = (n+1)S(n) + 2n \Longrightarrow \\ \frac{S(n+1)}{n+1} = \frac{S(n)}{n} + \frac{2}{n+1}.
$$
This shows that
$$
\frac{S(n)}{n} = \frac{2}{n} + \frac{2}{n-1} + \cdots + \frac{2}{2} + \frac{S(1)}{1} = 2H_n - 1 = \Theta(\log n),
$$
and so $S(n) = \Theta(n\log n)$.