1
$\begingroup$
    public static void sort(int[] A, int i, int j) {
        if (i >= j) return;

        int m = (i + j) / 2; 
        sort(A, i, m);
        sort(A, m + 1, j);

        if (A[m] > A[j]) {
            // swap A[j] and A[m]
            int temp = A[j];
            A[j] = A[m];
            A[m] = temp;
        }

        sort(A, i, j - 1);
    }

I tried the master theorem to find out the complexity of this function, but I guess it can't be used in this case. The algorithm seems to split the array in half, then it compares the element at index m with the element at index j and swaps them. However, the recursive call sort(A, i, j - 1) is confusing me. Can $T(n)=T(n/2)+T(n/2)+T(n-1)+O(1)$ be a possible solution?

$\endgroup$
0

2 Answers 2

4
$\begingroup$

Firstly, this is clearly a joke algorithm, AKA selection sort with extra steps -- you find the maximal element by splitting the array into halves, sorting them, and taking the maximum of the biggest element in each half.

Your recurrence relation is correct. Since only constant work is done at each branch, the time spent is proportional to the number of branches, which AFAICS is given by integer sequence A022905 in the OEIS.

You can easily see that this is a function that grows faster than any polynomial, by noting that $\lim_{n\rightarrow\infty}\frac{(n/2)^c + (n-1)^c}{n^c}$ is a constant larger than 1 for any $c$.

On the other hand, the function given by your recurrence relation grows by $O(n^{\log n})$ (try and see if you can figure out why), in other words it is a quasi-polynomial algorithm. I don't think this is the best analysis possible, though, as it looks like it grows even slower.

$\endgroup$
3
  • 1
    $\begingroup$ Indeed, this is the slowsort sorting algorithm. It is of humorous nature and not useful. It is a reluctant algorithm based on the principle of multiply and surrender (a parody formed by taking the opposites of divide and conquer). It was published in 1984 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis (a parody of optimal algorithms and complexity analysis). $\endgroup$ Feb 12 at 12:32
  • $\begingroup$ Using a spreadsheet, execution seems to take less then 2^(log_2 (n) / 2) steps. $\endgroup$
    – gnasher729
    Feb 13 at 18:04
  • $\begingroup$ @gnasher729 Which seems to fit the wikipedia's bound: you need $\epsilon>0$ for the lower bound to apply. $\endgroup$
    – rus9384
    Feb 13 at 23:12
1
$\begingroup$

Too long for a comment: If we call the number of calls for sorting an array with n items T(n), then T(1) = 1, and T(n) = T(n div 2) + T((n+1) div 2) + T(n-1) for n >= 2.

Assume that $T(n) = n^{c_n \cdot \log_2 n}$. Calculating $c_n$ by computer shows that $c_n$ gets smaller until $c_n = 0.432840$ when n = 716,727; then it becomes larger slowly; at $n = 18 \cdot 10^{9}$ we have about $c_n = 0.4394$. At this point $T(n)$ is just below $n^8$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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