4
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ You really mean final position, i.e., $2,3,4,5,6,7,8,9,1$ is not almost sorted? $\endgroup$ Nov 24 '15 at 16:56
  • $\begingroup$ Do you want specifically a non-parallel comparison sort? $\endgroup$
    – Arthur
    Nov 24 '15 at 16:59
  • $\begingroup$ @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. $\endgroup$
    – Andrew
    Nov 24 '15 at 17:02
  • $\begingroup$ @Arthur : As long as it can achieve O(n) time. $\endgroup$
    – Andrew
    Nov 24 '15 at 17:04
7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Arthur
    Nov 24 '15 at 17:02
  • $\begingroup$ It's actually $\sqrt{n}$ random elements. $\endgroup$
    – Andrew
    Nov 24 '15 at 17:25
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.