Introduction

Selection sort is easy to understand, but it is not stable in its usual form. Stability matters when two items have the same sort key and you want them to keep their original relative order, such as rows already ordered by a secondary field.

What Stability Means

A sorting algorithm is stable if equal keys stay in the same left-to-right order they had in the input. Imagine a list of students sorted by grade, where two students both have grade 90. If Alice appeared before Bob before sorting, a stable algorithm keeps Alice before Bob after sorting by grade.

That property becomes important when sorting records multiple times. A stable second sort preserves the grouping established by the first sort.

Why Standard Selection Sort Breaks Stability

Selection sort repeatedly finds the minimum element in the unsorted suffix and swaps it into the next output position. The problem is that a long-distance swap can move an earlier equal element behind a later equal element.

Consider records represented as (key, label):

items = [(4, "A"), (3, "B"), (3, "C"), (2, "D")]

On the first pass, selection sort finds (2, "D") and swaps it with the first element (4, "A"). The list becomes:

[(2, "D"), (3, "B"), (3, "C"), (4, "A")]

So far, nothing bad happened to the equal keys.

Now look at this input instead:

items = [(2, "A"), (1, "B"), (2, "C"), (1, "D")]

On the first pass, the minimum is (1, "B"), so it swaps with (2, "A"):

[(1, "B"), (2, "A"), (2, "C"), (1, "D")]

On the second pass, the minimum in the remaining suffix is (1, "D"), which swaps with (2, "A"):

[(1, "B"), (1, "D"), (2, "C"), (2, "A")]

Originally, (2, "A") came before (2, "C"). After sorting, (2, "C") is before (2, "A"). The equal keys changed order, so the algorithm is unstable.

A Minimal Implementation

The usual implementation makes the instability clear:

1def selection_sort(items):
2    items = items[:]
3    n = len(items)
4
5    for i in range(n):
6        min_index = i
7        for j in range(i + 1, n):
8            if items[j][0] < items[min_index][0]:
9                min_index = j
10        items[i], items[min_index] = items[min_index], items[i]
11
12    return items
13
14
15values = [(2, "A"), (1, "B"), (2, "C"), (1, "D")]
16print(selection_sort(values))

The algorithm is correct in terms of sorted order by key, but it does not preserve the sequence of ties.

How to Make a Selection-Style Sort Stable

A stable variant avoids swapping. Instead, it finds the minimum element, removes it, and shifts the intervening items right by one position. That preserves the order of equal elements.

1def stable_selection_sort(items):
2    items = items[:]
3    n = len(items)
4
5    for i in range(n):
6        min_index = i
7        for j in range(i + 1, n):
8            if items[j][0] < items[min_index][0]:
9                min_index = j
10
11        min_value = items[min_index]
12        while min_index > i:
13            items[min_index] = items[min_index - 1]
14            min_index -= 1
15        items[i] = min_value
16
17    return items
18
19
20values = [(2, "A"), (1, "B"), (2, "C"), (1, "D")]
21print(stable_selection_sort(values))

This keeps the relative order of equal keys, though it changes the movement cost profile of the algorithm.

Why This Matters Beyond Theory

In production code, stability matters when records are sorted by multiple fields in stages. For example, you might sort orders by timestamp and then stably sort by customer priority. An unstable algorithm can destroy the earlier ordering and produce output that is technically sorted by the final key but operationally wrong for reporting or display.

That is why languages often provide stable built-in sorts and why algorithm selection should consider more than time complexity.

Common Pitfalls

A common mistake is assuming that every comparison sort is stable unless documentation says otherwise. Stability is a separate property from correctness.

Another mistake is testing only with unique values. If every key is distinct, an unstable algorithm looks perfectly fine and the issue stays hidden.

Developers also confuse “not stable” with “incorrect.” Selection sort still sorts properly by key. The problem is only the ordering of tied records.

Finally, be careful when using custom objects. If equality on the sort key matters to downstream logic, choose a stable algorithm or add an explicit secondary key.

Summary

• Standard selection sort is unstable because it swaps the minimum element across long distances.
• Those swaps can move an earlier equal key behind a later equal key.
• Stability matters when the original order of ties carries meaning.
• A stable selection-style variant can be built by shifting elements instead of swapping.
• Always test sorting behavior with duplicate keys if stability is important.