(Solved): Consider the following recursive sorting algorithm. Algorithm WeirdSoRT (L, start, end ) : 1: i ...

Consider the following recursive sorting algorithm. Algorithm WeirdSoRT $$(L$$, start, end $$)$$ : 1: if end $$?$$ start $$=2$$ then 2: if $$L[$$ start $$]?L[$$ start $$+1]$$ then 3: Exchange $$L[$$ start $$]$$ and $$L[$$ start $$+1]$$. $$4:$$ end if 5: else if end-start $$>2$$ then 6: $$k:=($$ end $$?$$ start $$)$$ div 3 . $$7:$$ WEIRDSorT $$(L$$, start, end $$?k)$$. 8: WEIRDSorT $$(L$$, start $$+k$$, end $$)$$. 9: WEIRDSorT $$(L$$, start, end $$?k)$$. 10: end if Let $$n=?L?$$ be the length of the list being sorted by ParallezMergeSort. P2.1. Is WeIrpSort a stable sort algorithm? If yes, explain why. If no, show why not and indicate whether the algorithm can be made stable. P2.2. Prove via induction that WeIrdSont will sort list $$L$$. P2.3. Give a recurrence $$T(n)$$ for the runtime complexity of WerroSorT and solve the recurrence $$T(n)$$ by proving that $$T(n)?e(n)$$ for some expression $$e$$ that uses $$n$$.