Edit the RMarkdown source file 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.)
  1. 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.)