Let S(n) be the number of key comparisons done by MergeSort (Algorithm 4.5 on Page 175) when the keys are already sorted. (that
is, they are already exactly the way MergeSort will order them). Develop the recurrence relation, including boundary condition(s), for S(n). (This will be somewhat like the W(n) formula developed in the text for worst-case, but your S(n) is for the already-sorted-case.) Use the floor and ceiling operators as appropriate, and explain your reasoning.
