# Stable Partition

# 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.

```id="stable-partition"
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

```python id="stable-partition-python"
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)
```

```go id="stable-partition-go"
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)
}
```