Stable Partition

Stable partition rearranges an array so that elements satisfying a predicate appear before the others, while preserving relative order inside both groups.

You use it when grouping is required but original order still carries meaning.

Problem

Given an array $A$ of length $n$ and a predicate $P(x)$, reorder the array so that:

• all elements satisfying $P$ appear first
• all elements not satisfying $P$ appear after them
• relative order inside each group is preserved

Algorithm

Use two temporary arrays. Store matching elements in one array and non-matching elements in another, then concatenate them.

stable_partition(A, P):
    yes = empty array
    no = empty array

    for x in A:
        if P(x):
            append x to yes
        else:
            append x to no

    k = 0
    for x in yes:
        A[k] = x
        k += 1

    for x in no:
        A[k] = x
        k += 1

    return length(yes)

Example

Let

$$ A = [8, 3, 5, 2, 1, 4] $$

Partition by even numbers:

$$ P(x): x \bmod 2 = 0 $$

pass	element	group
1	8	yes
2	3	no
3	5	no
4	2	yes
5	1	no
6	4	yes

The stable groups are:

$$ yes = [8, 2, 4] $$

and

$$ no = [3, 5, 1] $$

Final array:

$$ [8, 2, 4, 3, 5, 1] $$

Return partition index $3$.

Correctness

The algorithm scans elements from left to right. Each element that satisfies $P$ is appended to yes in its original order. Each remaining element is appended to no in its original order.

Writing all elements from yes before all elements from no produces a valid partition, and each group keeps the same relative order as in the input.

Complexity

operation	time
scan input	$O(n)$
write output	$O(n)$
total	$O(n)$

Space usage:

$$ O(n) $$

An in-place stable partition is possible, but it is more complex and often slower in practice.

When to Use

Stable partition is appropriate when:

• elements must be grouped by a predicate
• relative order matters
• extra memory is acceptable
• predictable linear behavior is preferred

It is less suitable when memory must remain constant and stability is not required.

Implementation

def stable_partition(a, predicate):
    yes = []
    no = []

    for x in a:
        if predicate(x):
            yes.append(x)
        else:
            no.append(x)

    k = 0
    for x in yes:
        a[k] = x
        k += 1

    for x in no:
        a[k] = x
        k += 1

    return len(yes)

func StablePartition[T any](a []T, pred func(T) bool) int {
    yes := make([]T, 0)
    no := make([]T, 0)

    for _, x := range a {
        if pred(x) {
            yes = append(yes, x)
        } else {
            no = append(no, x)
        }
    }

    k := 0
    for _, x := range yes {
        a[k] = x
        k++
    }

    for _, x := range no {
        a[k] = x
        k++
    }

    return len(yes)
}