How to "sort" elements of 2 possible values in place in linear time? [duplicate]

Question

Suppose I have a function f and array of elements.

The function returns A or B for any element; you could visualize the elements this way ABBAABABAA.

I need to sort the elements according to the function, so the result is: AAAAAABBBB

The number of A values doesn't have to equal the number of B values. The total number of elements can be arbitrary (not fixed). Note that you don't sort chars, you sort objects that have a single char representation.

Few more things:

• the sort should take linear time - O(n),
• it should be performed in place,
• it should be a stable sort.

Any ideas?

---

Note: if the above is not possible, do you have ideas for algorithms sacrificing one of the above requirements?

Answer 1

If it has to be linear and in-place, you could do a semi-stable version. By semi-stable I mean that A or B could be stable, but not both. Similar to Dukeling's answer, but you move both iterators from the same side:

a = first A
b = first B
loop while next A exists
    if b < a
        swap a,b elements
        b = next B
        a = next A
    else
        a = next A

With the sample string ABBAABABAA, you get:

ABBAABABAA
AABBABABAA
AAABBBABAA
AAAABBBBAA
AAAAABBBBA
AAAAAABBBB

on each turn, if you make a swap you move both, if not you just move a. This will keep A stable, but B will lose its ordering. To keep B stable instead, start from the end and work your way left.

It may be possible to do it with full stability, but I don't see how.

Answer 2

A stable sort might not be possible with the other given constraints, so here's an unstable sort that's similar to the partition step of quick-sort.

1. Have 2 iterators, one starting on the left, one starting on the right.
2. While there's a B at the right iterator, decrement the iterator.
3. While there's an A at the left iterator, increment the iterator.
4. If the iterators haven't crossed each other, swap their elements and repeat from 2.