Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process
You are on the right track. 

Now that we have the recurrence relation $$S(n) = 2S(\frac{n}{2}) + \Theta(n\sqrt{n}),$$ Applying the case three of the master theorem, where $a=2$, $b=2$, $\epsilon=\frac12$, we will have $S(n)= \Theta( n\sqrt n)$. 

I was stretching a bit when we were applying the master theorem since the regularity condition, the existence of such $c&gt;0$ required for case three is not necessarily satisfied. What I really meant is that we can find two constant $0&lt;c_1&lt;c_2$ such that $c_1n\sqrt n\le S(n)-2S(\frac n2) \le c_2n\sqrt n$ for all $n$. Define $S_1$ by $S_1(n) = 2S_1(\frac{n}{2}) + c_1n\sqrt{n}$ and $S_2$ by $S_2(n) = 2S_2(\frac{n}{2}) + c_2 n\sqrt{n}$ with the same initial condition as $S$. Now we can apply case three of the master theorem to $S_1$ and $S_2$ to get the same $\Theta$ bound, since the regularity condition is satisfied with $1&gt;c=0.8&gt;\sqrt2/2$. Since $S_1(n)\le S(n)\le S_2(n)$, S(n) has the same $\Theta$ bound.

In case you have not learned/are not allowed to use the master theorem, you may have to more or less prove case three of the master theorem by yourself. You could find a proof, for example, in CLRS.