CareerCup

I'm thinking insertion sort for the first case.

For the second case, if it is mostly unsorted, then a standard mergesort or quicksort should do the job. If it is still mostly sorted (just not the extreme case given), then mergesort would probably be safest. In both of these second cases, radix sort could be best depending on the domain.

search for these glitches (unordered elements in nearly sorted array) and insert them at appropriate place(insertion sort on few elements)

Patience sorting? It gives a linear performance when data is pre-sorted. In case of only a few out-of-order elements, its performance will be close to linear.

For nearly sorted data insertion sort will be best. Let maximum displaced elements are k distance away. For ex. (3 2 1 4 6 5) k = 3. Then insertion sort will be O(kN).
If elements are nearly sorted like (3 4 5 2 1) few elements are n distance away and rest are sorted. Then also insertion sort will be O(kN)

Well, the way you wrote the example, I would wonder if the interview is actually asking about a rotated, linear data structure (e.g. rotated array or DLL).

If the answer is yes, then I would apply a binary search to identify the point of rotation (a situation in which the left element is greater than the adjacent, right element). Once the split point is a found, a series of shifts would occur for an array, or a single pointer adjustment for a DLL, in order to change to a sorted list.

O(lgn) to find + O(1) for a DLL
or
O(lgn) + O(n) for an array

This would be better than any comparison-based sorting.

Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

Partially sorted lists --> Insertion sort is winner.

bubble sort is the best for nearly sorted array