(a) Describe an algorithm that sorts an input array A[1..n] by calling a subroutine SQRTSORT(K), which...

 

Transcribed Image Text:

(a) Describe an algorithm that sorts an input array A[1..n] by calling a subroutine SQRTSORT(K), which sorts the subarray A[k+1..k+ n] in place, given an arbitrary integer k between 0 and n-n as input. (To simplify the problem, assume that n is an integer.) Your algorithm is only allowed to inspect or modify the input array by calling SQRTSORT; in particular, your algorithm must not directly compare, move, or copy array elements. How many times does your algorithm call SQRTSORT in the worst case? (b) Prove that your algorithm from part (a) is optimal up to constant factors. In other words, if f(n) is the number of times your algorithm calls SQRTSORT, prove that no algorithm can sort using of (n)) calls to SQRTSORT. (c) Now suppose SQRTSORT is implemented recursively, by calling your sorting algorithm from part (a). For example, at the second level of recursion, the algorithm is sorting arrays roughly of size n/4. What is the worst-case running time of the resulting sorting algorithm? (To simplify the analysis, assume that the array size n has the form 22", so that repeated square roots are always integers.) (a) Describe an algorithm that sorts an input array A[1..n] by calling a subroutine SQRTSORT(K), which sorts the subarray A[k+1..k+ n] in place, given an arbitrary integer k between 0 and n-n as input. (To simplify the problem, assume that n is an integer.) Your algorithm is only allowed to inspect or modify the input array by calling SQRTSORT; in particular, your algorithm must not directly compare, move, or copy array elements. How many times does your algorithm call SQRTSORT in the worst case? (b) Prove that your algorithm from part (a) is optimal up to constant factors. In other words, if f(n) is the number of times your algorithm calls SQRTSORT, prove that no algorithm can sort using of (n)) calls to SQRTSORT. (c) Now suppose SQRTSORT is implemented recursively, by calling your sorting algorithm from part (a). For example, at the second level of recursion, the algorithm is sorting arrays roughly of size n/4. What is the worst-case running time of the resulting sorting algorithm? (To simplify the analysis, assume that the array size n has the form 22", so that repeated square roots are always integers.)