Question: 13 (100 PTS.) Not a sorting network You are given an array AL .. n], but you can not access it directly (or even read

13 (100 PTS.) Not a sorting network You are given an array AL .. 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, for the following array 13.A. 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 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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
