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.