Consider the following algorithm

(a) What assumption(s) must be true about the array A such that SomeSort can correctly sort A given k.

(b) Prove that your assumption(s) is/are necessary: that is, for any array A which violates your assumption(s), SomeSort incorrectly sorts A.

(c) Prove that your assumption(s) from part a are sufficient. That is, prove the correctness of SomeSort under your assumption(s) from part a.

(d) Assuming that the assumption(s) from part a hold on A, prove a tight bound in terms of n and k on the worst-case runtime of SomeSort.

SomeSort(A, k): N-length (A) for i in [0,.. ,n-k] MergeSort(A,i,i+k-1)