I need help with solving 13B

You are given an array A1...n], but you can not access it directly (or even read the values in it, or compare them directly). Instead, you are give some procedures that can access the array and do certain operations. Your task is to sort the array (30 PTS.) You are given a procedure sortBlock(i), which sorts (in increasing order and in place), all the elements in Afi... ,i + u], where u 2 1 is a prespecified fixed parameter (i.e., u is a known fixed number between 1 and n, but it is not under your control). For example, 13.A. for the following array: 2.71828 18284 59045 23536 02874 7.1352 66249 With u 3, the call sort Block(2) would result in 2.71828 02874 18284 23536 59045 7.1352 66249 6 Describe an algorithm, that uses O((n/u)2) calls to sort Block, and sorts the array What is the running time of your algorithm if calling sortBlock takes O(1) time? (50 PTs.) Congratulations! You just got a better sorting primitives bMerge, copy, and a work array W[1,... ,n (i) copy can copy any block of length at most u+1 between the two arrays (or inside them) (ii) bMerge is weirder. It takes two blocks L and U (both with at most u +1 elements), 13.B. treat them as a single block, sort the unified block, and writes the smaller |L| elements (in sorted order) to L, and the other (larger) |U elements in sorted order to U (the two blocks do not have to be of the same length) For example, for 2.71828 182845904523536 02874 7.1352 66249 3 6 With u = 1, the call bMerge(/12 . . . 3],A[6. . .7) would result in: 2.71828 7.1352 18284 23536 02874 59045 66249 bMerge also returns the number of elements in original block L that are still in L after the operation is completed. In this example, since 18284 was in L before the operation, and it is in L after the operation is completed, the returned value would be 1 Note that the blocks given to bMerge can not overlap. Assume that All...n/2] and Aln/2 +1,...n] are already sorted (n is even). Describe an algorithm that performs a minimal total number of calls to sortBlock, copy and bMerge, and sorts the array A. What is the running time of your algorithm if calling sortBlock, copy and bMerge takes O(1) time? (Prove your bound.) berge tales 00) tina if eaoinensd You are given an array A1...n], but you can not access it directly (or even read the values in it, or compare them directly). Instead, you are give some procedures that can access the array and do certain operations. Your task is to sort the array (30 PTS.) You are given a procedure sortBlock(i), which sorts (in increasing order and in place), all the elements in Afi... ,i + u], where u 2 1 is a prespecified fixed parameter (i.e., u is a known fixed number between 1 and n, but it is not under your control). For example, 13.A. for the following array: 2.71828 18284 59045 23536 02874 7.1352 66249 With u 3, the call sort Block(2) would result in 2.71828 02874 18284 23536 59045 7.1352 66249 6 Describe an algorithm, that uses O((n/u)2) calls to sort Block, and sorts the array What is the running time of your algorithm if calling sortBlock takes O(1) time? (50 PTs.) Congratulations! You just got a better sorting primitives bMerge, copy, and a work array W[1,... ,n (i) copy can copy any block of length at most u+1 between the two arrays (or inside them) (ii) bMerge is weirder. It takes two blocks L and U (both with at most u +1 elements), 13.B. treat them as a single block, sort the unified block, and writes the smaller |L| elements (in sorted order) to L, and the other (larger) |U elements in sorted order to U (the two blocks do not have to be of the same length) For example, for 2.71828 182845904523536 02874 7.1352 66249 3 6 With u = 1, the call bMerge(/12 . . . 3],A[6. . .7) would result in: 2.71828 7.1352 18284 23536 02874 59045 66249 bMerge also returns the number of elements in original block L that are still in L after the operation is completed. In this example, since 18284 was in L before the operation, and it is in L after the operation is completed, the returned value would be 1 Note that the blocks given to bMerge can not overlap. Assume that All...n/2] and Aln/2 +1,...n] are already sorted (n is even). Describe an algorithm that performs a minimal total number of calls to sortBlock, copy and bMerge, and sorts the array A. What is the running time of your algorithm if calling sortBlock, copy and bMerge takes O(1) time? (Prove your bound.) berge tales 00) tina if eaoinensd