Sorting almost sorted array
If you have an array with a sequential range that covers all but k elements, and you know the range, then you sort the k elements in O (k log k), then merge two ranges that you know to be sorted in O (n). That sorts the whole array in O(n) as long as k is O (n / log  n). 

In your case k = $O (n^{1/2})$ so clearly you can sort the array in O (n). 

And you don't need to know the sorted range, because for large n we have n/2 inside the sorted range, so you can just count the elements in ascending / descending order from n/2 upwards / downwards.