An array $A$ of size n is known to be sorted except for the first $k$ elements and the last $k$ elements, where $k$ is a constant. Which of the following algorithms will be the best choice for sorting the array $A?$
Why not quick sort will be answer? Quick Sort sorts part by part using pivot. So, why not will it be answer?? How do we know it is asking for almost sorted array??
Well it looks like we are doing insertion sort algo. and its T.C. will be O(n*k) and since k is constant it will be O(n).