2
$\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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\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$ Commented Feb 12, 2024 at 12:32
  • $\begingroup$ Using a spreadsheet, execution seems to take less then 2^(log_2 (n) / 2) steps. $\endgroup$ Commented Feb 13, 2024 at 18:04
  • $\begingroup$ @gnasher729 Which seems to fit the wikipedia's bound: you need $\epsilon>0$ for the lower bound to apply. $\endgroup$ Commented Feb 13, 2024 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$.

Improve this answer
$\endgroup$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.