# 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)$.

• This is still assuming it's a comparison sort that is not done in parallel. For instance, bucket sort might, depending on what you're sorting, be linear no matter what the initial state of the list is. Nov 24 '15 at 17:02
• 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)$.