O(nlogn) in-place sorting algorithm

Question

This question was in the preparation exam for my midterm in introduction to computer science.

There exists an algorithm which can find the kth element in a list in O(n) time, and suppose that it is in place. Using this algorithm, write an in place sorting algorithm that runs in worst case time O(n*log(n)), and prove that it does. Given that this algorithm exists, why is mergesort still used?

I assume I must write some alternate form of the quicksort algorithm, which has a worst case of O(n^2), since merge-sort is not an in-place algorithm. What confuses me is the given algorithm to find the kth element in a list. Isn't a simple loop iteration through through the elements of an array already a O(n) algorithm?

How can the provided algorithm make any difference in the running time of the sorting algorithm if it does not change anything in the execution time? I don't see how used with either quicksort, insertion sort or selection sort, it could lower the worst case to O(nlogn). Any input is appreciated!

Answer 1

Check wiki, namely the "Selection by sorting" section:

Similarly, given a median-selection algorithm or general selection algorithm applied to find the median, one can use it as a pivot strategy in Quicksort, obtaining a sorting algorithm. If the selection algorithm is optimal, meaning O(n), then the resulting sorting algorithm is optimal, meaning O(n log n). The median is the best pivot for sorting, as it evenly divides the data, and thus guarantees optimal sorting, assuming the selection algorithm is optimal. A sorting analog to median of medians exists, using the pivot strategy (approximate median) in Quicksort, and similarly yields an optimal Quicksort.

The short answer why mergesort is prefered over quicksort in some cases is that it is stable (while quicksort is not).