# Converting a recursive algorithm to a runtime function [closed]

void Sort(int A[], int left, int right)
{
int p;

if (left < 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.

• Tried anything? – G. Bach Nov 12 '13 at 12:59
• This may help you stackoverflow.com/questions/2709106/… – Anton Nov 12 '13 at 13:00
• What did you write down, where did it go wrong? – G. Bach Nov 12 '13 at 13:05
• Do you understand that for the purpose of $\Theta$-analysis, most individual lines can be compacted to cost $1$? – Raphael Nov 12 '13 at 16:49
• @Quaker I suggest you translate the algorithm line by line and show us your result. Then we can figure out where your problem lies. – Raphael Nov 12 '13 at 16:52

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.

• Master Theorem actually solves this like a magic but I need to solve it by using the recurrence on itself until I find a pattern which is insanely confusing. – Eran Nov 13 '13 at 10:42

Hint: Usual merge sort takes a list of size $n$, divides it into two halves, sorts the two halves recursively, then merges them in $O(n)$. Your routine take a list of size $n$, divides it into three thirds, sorts the first two recursively and the last one using mergesort (this detail is a bit strange; you'd expect all three parts to be sorted recursively), then merges them in $O(n)$.