5
$\begingroup$

Given an array with only 0 & 1. Can we have an algorithm which has all the following desirable characteristics-

  • The algorithm runs in $O(n)$ time.

  • The algorithm is stable.

  • The algorithm sorts in place.

I know the algorithms if only 2 characteristics are required but want to know if all the three characteristics possible simultaneously or not? If yes, how?

$\endgroup$
  • 2
    $\begingroup$ What does stable mean when there is only 0 & 1? $\endgroup$ – greybeard Feb 3 '17 at 10:58
  • 1
    $\begingroup$ Means the order of zeros relative to zeros and ones relative to ones is preserved after the sort. $\endgroup$ – user3853544 Feb 3 '17 at 19:10
  • 2
    $\begingroup$ This paper achieves stable zero/one sorting in O(n) word operations (without a multiplication operation) with O(1) words of auxiliary memory. ​ ​ ​ (See ​ "The elements are regarded ... produces 7v$\supseteq$2$^i$8." .) ​ ​ ​ ​ ​ ​ ​ (continued ...) ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Feb 4 '17 at 11:22
  • 2
    $\begingroup$ (... continued) ​ ​ ​ I don't know whether-or-not that can be improved to O(n) time or whether-or-not the space usage can be reduced, even for just usual-meaning-of-stable-sorting of elements of {0,1,2} with respect to the total preorder ​ 0 < 1 $\sim$ 2 . ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Feb 4 '17 at 11:22

Your Answer

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

Browse other questions tagged or ask your own question.