S1 is False, S2 is True
Notice that:
- Any element initially at an even index, will always remain at an even index. Similarly, any element initally at an odd index will remain at an odd index.
- An even indexed element is not compared with any element at an odd numbered index in one iteration of rumblesort.
- Using A and B we have a stronger claim that any element initially at an even index can "never" be compared to an element initially at any odd index.
S1: C is sufficient to tells us that Rumble sort is incorrect, that is, it doesn't work correctly for all inputs.
example input where Rumblesort fails: [2, 1, 3]
S2: To verify whether Rumblesort will work correctly for a given input I, we can sort all even indexed elements of I and all odd elements of I separately. Let these sorted lists be $\rm{EVEN}$ and $\rm{ODD}$. Then, Rumblesort fails if $\exists i: \exists j < i: \rm{ODD}[j] > \rm{EVEN}[i]$, or if $\exists j: \exists i < j: \rm{EVEN}[i] > \rm{ODD}[j]$
This verification takes $\Theta (n \log n)$ time for the two sorts, and $\mathcal O(n^2)$ time for each of those checks, totaling $\mathcal O (n^2)$ time.
Note: The checks can be done in $\mathcal O(n \log n)$ by using binary search, so the most efficient checking algorithm can do it in $\Theta (n \log n)$ time.