The use of sentinels in algorithm merge requires the availability of an additional cell in the arrays to be merged; see Section 7.4.1. Although this is not an issue when merge is used within mergesort, it can be a nuisance in other applications. More importantly, our merging algorithm can fail if it is not possible to guarantee that the sentinels are strictly greater than any possible value in the arrays to be merged. (a) Give an example of arrays U and v that are sorted but where the result of merge (U, V, T) is not what it should be. What is the contents of T after this pathological call? (You are allowed the value infinity in arrays U and V and you may wish to specify the values of U and V outside the bounds of the arrays.) (b) Give a procedure for merging that does not use sentinels. Your algorithm must work correctly in linear time provided the arrays U and V are sorted prior to the call. Sorting my merging The obvious divide-and-conquer approach to this problem consists of separating the array T into two parts whose sizes are as nearly equal as possible, sorting these parts by recursive calls, and then merging the solution for each part, being careful to preserve the order. To do this, we need an efficient algorithm for merging two sorted arrays U and V into a single array T whose length is the sum of the lengths of U and V. This can beta achieved more efficiently - and more easily - if additional storage is available at the end of both the arrays U and V to beta used as a sentinel. (This technique works only if we can set the sentinel to a value guaranteed to beta bigger than every element in U and V, which we denote below by "infinity"; see problem 7.13) Procedure merge(U[1..m + 1], V[1..n + 1], T[1..m + n]) {merges sorted arrays U[1..m] and V[1..n] into T[1..m + n]); U[m + 1] and V[n + 1] are used are sentinels} I, j-1 U[m + 1], V[n + 1] - infinity fork - 1 to m + n do if U[i]