# 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.

• "Item two works." Have you checked when $n=4$, the first case when it might make a difference? – John L. May 20 '19 at 4:02
• "Any pair of items is never swapped more than once" means exactly what it means. For example, suppose we just swapped (5,3) to be (3,5). Then 3 will always be before 5 from now on. The pair $\{5,3\}$ will not be swapped any more. – John L. Jun 5 '19 at 20:56

• 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.
• 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 such that $$\pi(j)<\pi(i)$$. A permutation can have at most $$\binom{n}{2}$$ inversions (this is the number of pairs $$i < j$$). Each swap operation reduces the number of inversions by 1.
• Thanks for your help!. It is correct for bullet 4 to say that if reorganizing the array takes linear time, the recurrence would be: $C (n) = 3C (2n / 3) + O (n)$?, to which applying the master theorem will result in: $C (n) = \Theta (n ^ {\ log_ {3/2} 3})$ – FredieF May 21 '19 at 17:01
• The exact recurrence depends on implementation details. If you implement it using pointers, you can improve $O(n)$ to $O(1)$. – Yuval Filmus May 21 '19 at 17:03