3. Collaborative Problem. CLRS 8-7 The 0-1 Sorting Lemma and Column Sort: A compare-erchange operation on two array elements Ali] and Ali, where i Aj] then exchange Ali] with A] After the compare-xchange operation, we know that Ai A An oblivious compare-erchange algorithm operates solely by a sequence of pre-specified compare-exchange operations. The indices of the positions compared in the sequence must be determined in advance, and although they can depend on the number of elements being sorted, they cannot depend on the values being sorted, nor can they depend on the result of any prior compare-exchange operation. For example, here is insertion sort expressed as an oblivious compare-exchange algorithm: INSERTIONSORT(A) for j2 to A.length do for i ?j-1 downto 1 do COMPAREEXCHANGE (A. i, i + 1) The 0-1 sorting lemma provides a powerful way to prove that an oblivious compare-exchange al- gorithm produces a sorted result. It states that if an oblivious compare-exchange algorithm correctly sorts all input sequences consisting of only Os and 1s, then t correctly sorts a inputs comtaining arbitrary values You will prove the 0-1 sorting lemma by proving its contrapositive: if an oblivious compare-exchange algorithm fails to sort an input containing arbitrary values, then it fails to sort some 0-1 input. Assume that an oblivious compare-exchange algorithm X fails to correctly sort the array A1..n]. Let AlPl be the smallest value in A that X puts into the wrong location, and let A be the value that algorithm X moves to the location into which Alpl should have gone. Define array B[1.of s and 1s as follows: Bj-O if Ali]s Alpl if Ai >Ap After you prove the 0-1 sorting lemma (in step (b) below), you will use the 0-1 sorting lemma to prove that a particular sorting algorithm works correctly. The algorithm columnsort works on a rectangular array of n elements. The array has r rows and s columns (so that n rs), subject to three restrictions r must be even e s must be a divisor of r, and When columnsort completes, the array is sorted in column-major order: reading down the columns, from left to right, the elements monotonically increase. Columnsort operates in eight steps, regardless of the value of n. The odd steps are all the same: sort eac h column individually. Each even step is a fixed permutation. Here are the steps: . Sort each column Transpose the array, but reshape it back to r rows and s columns. In other words, turn the leftmost column into the top r/s rows, in order; turn the next column into the next r/s rows, in order: and so O