Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG
How does the recursive formula for $E[T(n)]$ compare between this algorithm and randomized quicksort? They are very similar, which might lead one to believe that the running time of your algorithm is $\Theta(n \log n)$. In fact, the recursive formula for the run-time is so similar to the one for quicksort, that you could use that fact in itself as a proof. There are more elegant ways to prove it, but you can also prove it by induction.

$$ T(n) \leq bn + \frac{1}{n}\sum_{k = 1}^n T(k) + T(n-k)
$$ 

$$ = bn + \frac{2}{n}\sum_{k = 1}^{n-1} T(k).
$$

Suppose (induction hypothesis) that $T(i) \leq ci \ln i$ for $i \le n - 1$.

Then use the standard trick of bounding a sum by an integral:
$\sum_{i=1}^{n-1}f(i) \leq \int_1^n f(x) dx$.

The rest of the proof works like a standard proof by induction with just a little algebra.

Here's a nice source for this and other proofs of the running time of quicksort, and the techniques apply to this problem as well.

Notes on randomized quicksort analysis