0
$\begingroup$
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.

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Eran Nov 13 '13 at 10:42
0
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.