An array of size n is known to be sorted except for the 1st k elements and the last k elements, where k is a constant. which of the following algorithm is the best choice for sorting the array A?
Quick Sort or Insertion Sort?
given answer is the insertion sort, and i know it should be true too. but why not quick sort?
just apply quick sort two times--- one for the starting k elements and other for the end k elements(since we know the value of k), and it will take O(klogk) in average case and O(k^2) in the worst case. what’s wrong in that?