SomeSort (A, b, e) if e = b + 1 then if A[b]> A[e] then end if else if e> b+ 1 then Consider the following very simple and elegant(?) sorting algorithm: exchange A[b] and A[e] end if p [e-b+] SomeSort (A,b, e - p) SomeSort (A,b+p, e) SomeSort (A, b, e - p) a. Does SomeSort correctly sort its input array A (assuming that n e-b+1 is the length of the array)? Justify your answer. b. Consider the input array A: 8 1 4 973 2 6 5. List five valid states of the array during the execution of the algorithm. C. Find a recurrence for the worst-case running time of SomeSort. Give a tight (i.e. e) asymptotic bound for the worse-case running time of SomeSort (Hint: consider n = 3k for some k). d. By comparing SomeSort with insertion sort and merge sort, argue if this simple algorithm is efficient.