A Rather Poor Merge Sort
Ryan is implementing a merge sort algorithm that he heard about in computers class. However, he wasn't paying attention, and ended up implementing the merge sort in a very unusual way.
The standard merge sort takes a list, and recursively splits it in half, until there is only one element left. It then uses the idea that two sorted lists can be easily merged in \(O(n)\) time using "two pointer technique" (this step is usually called
Ryan doesn't know about two pointer technique, however, so he decided to replace
merge with a bubble sort! The bubble sort runs in \(O(n^2)\) time.
What is the runtime of this merge sort implementation?