3. Stoo-Sort Lara, Curry, and Joe are clever algorithmists who are vying to get coveted jobs at Moogle. They claim that they can do better than O(n log2 n) for sort, using this one neat trick: Stoo-Sort SomeList: If SomeList is length 1 or 0, Stop. If SomeList[0] > SomeList (End), Swap! If there are 3 or more elements in SomeList: Stoo-Sort the initial 2/3 of SomeList Stoo-Sort the final 2/3 of SomeList Stoo-Sort the initial 2/3 of SomeList again(!). (a) Show that Stoo-Sort is correct for an arbitrary SomeList. For convenience, you can assume that the size of SomeList is a power of 3. (b) Derive a recurrence to determine the worst case running time of Stoo-Sort. What is the bound? Will our illustrious algorithmists get that Moogle job? 3. Stoo-Sort Lara, Curry, and Joe are clever algorithmists who are vying to get coveted jobs at Moogle. They claim that they can do better than O(n log2 n) for sort, using this one neat trick: Stoo-Sort SomeList: If SomeList is length 1 or 0, Stop. If SomeList[0] > SomeList (End), Swap! If there are 3 or more elements in SomeList: Stoo-Sort the initial 2/3 of SomeList Stoo-Sort the final 2/3 of SomeList Stoo-Sort the initial 2/3 of SomeList again(!). (a) Show that Stoo-Sort is correct for an arbitrary SomeList. For convenience, you can assume that the size of SomeList is a power of 3. (b) Derive a recurrence to determine the worst case running time of Stoo-Sort. What is the bound? Will our illustrious algorithmists get that Moogle job