OBLEM 4: analysis (50 points): ceis a "Divide-And conquer" sorting Algorithm We will call Here SILLY SORT If ns2, sort the elements by making at most one comparison and a (possible) swap. Otherwise: (1) Recursively silly_sort the last two thirds of the array (rounding up). (Ceiling of 2n/3elements). (2) Recursively silly sort the first two thirds of the array (again rounding up) (3) Recursively silly sort the last two thirds of the array (again rounding up). Your job: you have two tasks: I. (20 points) Argue the correctness of the algorithm. (Think about what must be true after step 1; then what must be true after step 2). Your argument does not need to be a formal proof, but it should be "inductive" II. Analysis: A. (15 points) Write a recurrence relation expressing the runtime of SILLY SORT Your recurrence relation will be of the form "T(N) B. (10 points) Do some research on the internet on the "Master Theorem." Apply the Master Theorem to your answer to (A) to derive a tight runtime bound for SILLY-SORT (i.e., a . bound) slower, faster or equivalent to that of Selection Sort? Explain. c. (5 points) Is the runtime of SILLY_SORT asymptotically