Finding the Median and an Application to Sorting
In the previous few entries we’ve been discussing quick_sort and analyzing the run-time complexity of recursive algorithms. We’re going to apply what we’ve learned so far to finding the median of an array in O(n) time. Then we’re going to see how that can be added to quick_sort to guarantee that it finishes in O(nlog_2(n)) time.