# Stable Selection Sort

# Stable Selection Sort

Stable selection sort modifies selection sort to preserve the relative order of equal elements. Instead of swapping the minimum element into position, it removes the minimum and shifts the intervening elements right by one position.

This ensures stability at the cost of additional data movement.

## Problem

Given a sequence $A$ of length $n$, reorder it such that

$$
A[0] \le A[1] \le \cdots \le A[n-1]
$$

and equal elements retain their original relative order.

## Algorithm

For each position $i$, find the minimum element in $[i, n-1]$. Store it, shift all elements between $i$ and its position one step to the right, then insert the minimum at position $i$.

```id="z4k1p8"
stable_selection_sort(A):
    n = length(A)
    for i from 0 to n - 1:
        min_index = i
        for j from i + 1 to n - 1:
            if A[j] < A[min_index]:
                min_index = j

        key = A[min_index]

        while min_index > i:
            A[min_index] = A[min_index - 1]
            min_index = min_index - 1

        A[i] = key
```

## Example

Let

$$
A = [(4,a), (2,b), (2,c), (3,d)]
$$

where the second component indicates original order.

Step 1:

Minimum is $(2,b)$

Shift elements:

→ [(2,b), (4,a), (2,c), (3,d)]

Step 2:

Minimum in remaining is $(2,c)$

→ [(2,b), (2,c), (4,a), (3,d)]

Final result:

$$
[(2,b), (2,c), (3,d), (4,a)]
$$

Relative order of equal keys is preserved.

## Correctness

At each iteration, the smallest remaining element is inserted at position $i$. Since elements are shifted rather than swapped, no equal elements change their relative order. The invariant that the prefix is sorted and stable holds throughout execution.

## Complexity

| case    | comparisons        | time     |
| ------- | ------------------ | -------- |
| best    | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| worst   | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| average | $\frac{n(n-1)}{2}$ | $O(n^2)$ |

Shifting increases the number of assignments, but asymptotic time remains:

$$
O(n^2)
$$

Space complexity:

$$
O(1)
$$

## Properties

* stable
* in-place
* more writes than standard selection sort

## When to Use

This variant is useful when stability is required but selection sort’s structure is preferred, such as in constrained environments where auxiliary memory must remain constant.

## Implementation

```id="q2m7x5"
def stable_selection_sort(a):
    n = len(a)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j

        key = a[min_idx]
        while min_idx > i:
            a[min_idx] = a[min_idx - 1]
            min_idx -= 1
        a[i] = key

    return a
```

```id="v9k3z1"
func StableSelectionSort[T constraints.Ordered](a []T) {
    n := len(a)
    for i := 0; i < n; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if a[j] < a[minIdx] {
                minIdx = j
            }
        }

        key := a[minIdx]
        for minIdx > i {
            a[minIdx] = a[minIdx-1]
            minIdx--
        }
        a[i] = key
    }
}
```