Sorting almost sorted array in $O(n)$ time

Question

What is the best way to sort an array that has at least half of its elements in their final position? Is it possible to achieve $O(n)$ running time?

Answer 1

$O(n)$ is not possible as your initial position might be $\frac n2$ small items in correct order followed by $\frac n2$ items in random order. Sorting the latter takes $O(n\ln n)$.

Answer 2

I think we can get an improvement to linear time if only $\frac{n}{\log{n}}$ items are out of place. First, pick out the misplaced items (they will occur in runs where the endpoints do not compare correctly with a neighbor), this takes linear time. Then use binary search on the remaining correctly-sorted items to find the correct positions for each misplaced item, this takes $O(\log{n})$ time for each item, so the total time is $O(n)$.