# Sorting in place & stable in linear time

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?

• What does stable mean when there is only 0 & 1? – greybeard Feb 3 '17 at 10:58
• Means the order of zeros relative to zeros and ones relative to ones is preserved after the sort. – user3853544 Feb 3 '17 at 19:10
• 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 ...) ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ – user12859 Feb 4 '17 at 11:22
• (... 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 . ​ ​ ​ ​ ​ ​ ​ – user12859 Feb 4 '17 at 11:22