title: O(nlogn) in-place sorting algorithm
body: <p>This question was in the preparation exam for my midterm in introduction to computer science. </p>
  
  <blockquote>
    <p>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?</p>
  </blockquote>
  
  <p>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?</p>
  
  <p>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!</p>