By the statement of the question i am trying to generalize the structure of the array.for me Being at their correct position means they can't be shifted. I tried to come up with a few examples and deducted such an array has to be 2-sorted or all the sorted elements are in the first half. for a k-sorted array we can use insertion sort or heap sort with a heap of size k,  but first i need to make some generalization about the structure of the array. How do we go about proving it formally?  Intuitive explanation would work too. 
Sorting an array where half of the elements are at their correct position
algorithms;sorting;arrays