Converting a recursive algorithm to a runtime function void Sort(int A[], int left, int right)
{
    int p;

    if (left &lt; right)
    {
        p = (right + left + 2)/3;

        Sort(A, left, left+p-1);
        Sort(A, left+p, left+2*p-1);

        MergeSort(A, left+2*p, right);

        Merge3(A, left, left+p, left+2*p, right);
    }
}


I need to convert this function into a mathematical expression in order to solve it's run-time complexity.

I know  that MergeSort()'s complexity is of $\Theta(n \log n)$ and that Merge3()'s complexity is of $\Theta(n)$.

I can't figure how to transform this into a recursive mathematical expression.
The key is to use right - left as $n$ for the parameter of the runtime recursion. What is the size of the subparts?

Closer hint:


   Note that the algorithm separates the input part of the array in three approximately equal-sized parts; the first two are sorted recursively, the third with Mergesort. This should be reflected in your recurrence.


Almost finished:


   Assuming Merge3 runs in time $\Theta(n)$ und MergeSort in time $\Theta(n \log n)$, you get a recurrence of the form

 $\qquad\displaystyle T(n) \approx 2T(n/3) + \Theta(n) + \Theta(n/3 \log(n/3))$

 since all parts have size $\approx p \approx n/3$. Solve this with the Master theorem and flesh out the details.