How to understand the recurrence relation and time-complexity of StoogeSort?

I have the following problem of recurrences and divide-and-conquer. Consider the algorithm, called StoogeSort in honor of the immortals Moe, Curly and Larry. The swap operation $(x,y)$ exchanges the values ​​of $x$ and $y$.

Algorithm StoogeSort:
procedure StoogeSort(A[0...n −1])
    if n = 2 ∧ A[0] > A[1] then
        swap(A[0], A[1])
    else if n > 2 then
        m = ceil(2n/3)
        StoogeSort(A[0...m−1])
        StoogeSort(A[n−m ...n−1])
        StoogeSort(A[0...m−1])
    end
end

The problem demands the following:

• Show that the algorithm correctly orders the array A of n elements.

• Would it work correctly if we replaced ceil($\frac{2n}{3}$) with floor($\frac{2n}{3}$)? Justify your answer.

• Give a recurrence for the number of comparisons between elements of A that StoogeSort performs with n elements.

• Solve the recurrence for the number of comparisons. (Hint: skip functions ceil and functions floors, solve exactly the result.)

• Show that you execute at most $ {n}\choose{2} $ swap operations. (Hint: How many comparisons are required to locate the element in position k if it is at start?)

I intuit that item two works changing ceil by floor so if the length of the arrangement is odd it does not matter if I take the larger half at the beginning or after the middle of the arrangement. But how do I show this?

I have the following help:

For the first bullet, use induction: It is easy to see it works for 1 or 2 items. Prove that if it works for $n−1$ or fewer items, then it also works for n items. For the 3rd & 4th bullets, $c_1=0$, $c_2=1$ and $c_n=3c_m$. For the final bullet, show that any pair of items is never swapped more than once.

How should I interpret the help for bullets 4 and 5? Thanks in advance.

Here are some more hints:

• The algorithm partitions the array $A$ into three parts $B,C,D$ such that $|C| \geq |B|,|D|$ and then sorts $BC$ (the array formed by the first two parts), $CD$ (the array formed by the last two parts), and then $BC$ again. Show that for any such partition, the result is sorted. You can use the 0-1 principle.

• When $n=4$, the algorithm sorts $a_1,a_2$, then $a_3,a_4$, then $a_1,a_2$. You can easily give an example showing that this doesn't work.

• You should be able to solve this yourself.

• The recurrence in the preceding bullet involves $m = \lceil \frac{2n}{3} \rceil$. This part asks you to replace $m$ with $\frac{2n}{3}$, and then solve the recurrence using the master theorem.

• For a permutation $\pi$, the number of inversions is the number of pairs $i

StackExchange Computer Science Q#109575, answer score: 3