3. Stoo-Sort(25 points) 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 logan) for sort, using this one neat trick: O ONO 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 e bound? Will our illustrious algorithmists get that Moogle job