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

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?

• You really mean final position, i.e., $2,3,4,5,6,7,8,9,1$ is not almost sorted? Nov 24 '15 at 16:56
• Do you want specifically a non-parallel comparison sort? Nov 24 '15 at 16:59
• @HagenvonEitzen : I meant 1,2,3,4,5,6,7,10,9,8. 1 to 7 is already sorted but the last part is not. Nov 24 '15 at 17:02
• @Arthur : As long as it can achieve O(n) time. Nov 24 '15 at 17:04

$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)$.
• It's actually $\sqrt{n}$ random elements. Nov 24 '15 at 17:25
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)$.