Edit the [RMarkdown source file](04cavarrettasort.Rmd) for this assignment in RStudio. Enter your responses after each question. When you finish, Knit the file to HTML and upload the `.html` output to Canvas.

Cubs legend Phil Cavarretta wore uniform number 3 during his MVP season in 1945, when he led the Cubs to their second-most recent pennant. The following sorting algorithm is named in honor of him.

```
CavarrettaSort(A[0 .. n - 1]):
    if n = 2 and A[0] > A[1]
        swap A[0] and A[1]
    else if n > 2
         m = ceiling(2n/3)
         CavarrettaSort(A[0 .. (m - 1)])
         CavarrettaSort(A[(n - m) .. (n - 1)])
         CavarrettaSort(A[0 .. (m - 1)])
```

> 1. Prove that (explain why) `CavarrettaSort(A[0 .. n − 1])` correctly sorts its input array, for all $n\geq 2$. (It isn't obvious that it does; your proof should convince someone (who isn't quite as clever as you are) that the algorithm actually works.)



> 2. Give a recurrence for $C(n)$, the number of list comparisons performed by `CavarrettaSort(A[0 .. n - 1])`. (Note that `A[0] > A[1]` is a list comparison, but `n > 2` is not.)



