Problem (page limit: 3 pages) A ssume that n is a power of two. Consider the following sorting algorithm: STRAIGHTEN(A1 T) : if 2 then ifA[2]A111 then swap A A2 3: 4: end if 5: else WEIRDSORT(A1..T 1: ifn > 1 then 3 WEIRDSORT(A s: end if WEIRDSORT(All .. 6: fori1 to T do ) STRAIGHTEN(A1..) 8 end for 9: STRAIGHTEN (A1 STRAGHTEN (14+1,n/) STRAIGHTEN (AT1 10: 12: end if . Give an example proving that WEIRDSORT would not correctly sort if we removed lines 6-8 in STRAIGHTEN. 2. Give an ex ample proving that WEIRDSORT would not correctly sort if we swapped lines 10 & 11 in STRAIGHTEN 3. Prove by induction that WEIRDSORT correctly sorts any input array (of size a power of two). (Hint: Formulate a claim for what STRAIGHTEN 1s supposed to accomplish, and prove it.) 4. Write a recurrence to count the number of comparisons made by STRAIGHTEN on an array of size . Write a recurrence to count the number of comparisons made by WEIRDSORT on an array of size . Solve these two recurrences to obtain an asymptotic expression for the number of comparisons done by STRAIGHTEN and by WEIRDSORT. No need to show your calculations