Basic

Stability and ties

When two items compare equal, stability decides whether they keep their original order. A stable sort keeps them, and that is what lets you sort by several fields in steps.

What you will see

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Check stability and multi-field sorting.

Sort tied rows.

rows = [[2, "a"], [2, "b"]] print(sorted(rows))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

[[2, "a"], [2, "b"]]

Sort by two fields, least first.

rows = [(2, "b"), (1, "a"), (2, "a")] rows.sort(key=lambda r: r[1]) rows.sort(key=lambda r: r[0]) print(rows)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

[(1, "a"), (2, "a"), (2, "b")]

Show built-in keeps ties.

print(sorted([2, 2, 1]))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

[1, 2, 2]

Read the first tie label.

rows = [(1, "x"), (1, "y")] print(rows[0][1])

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

A stable sort keeps equal items in their original order, which is what lets you sort by several fields one at a time.

1 items tie on a field

↓

2 stable keeps input order

↓

3 sort least field first

↓

4 multi-field order works

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

rows = [[2, "a"], [2, "b"]] sets nothing on screen

print(sorted(rows)) [[2, "a"], [2, "b"]]

Why this works

Stability is a guarantee

A stable sort promises equal items keep their input order. That promise is what makes multi-key sorting by repeated sorts correct.

Sort least first

To order by several fields, sort by the least important first, then up to the most important. Stability carries the lower orders through the ties.

Examples

Equal items

rows = [[2, "a"], [2, "b"]]
print(sorted(rows))

Two rows tie on the first field. A stable sort keeps a before b, the order they arrived.

Sort by two fields

rows = [(2, "b"), (1, "a"), (2, "a")]
rows.sort(key=lambda r: r[1])
rows.sort(key=lambda r: r[0])
print(rows)

Sort by the last field first, then the first. Stability makes the first sort keep the second order inside ties.

Unstable breaks it

rows = [[2, "a"], [2, "b"]]
print(rows[0])

An unstable sort may swap the tied pair. Then the second-field order is lost.

Built-in is stable

print(sorted([2, 2, 1]))

Python sorted is stable. Equal values keep their input order, which the multi-field trick relies on.

Ties keep meaning

rows = [(3, "late"), (3, "early")]
print(sorted(rows, key=lambda r: r[0]))

The tie keeps the earlier record first. Stability preserves a meaning the number alone drops.

Stable by field

rows = [("b", 1), ("a", 2), ("b", 0)]
rows.sort(key=lambda r: r[1])
print(rows)

Sorting by number keeps the letter order inside equal numbers. That is stability in action.

Order of sorts

rows = [(2, 1), (1, 2), (2, 0)]
rows.sort(key=lambda r: r[1])
rows.sort(key=lambda r: r[0])
print(rows)

Sort least important field first. Each stable sort layers on the one before.

When it matters

rows = [(1, "x"), (1, "y")]
print(rows[0][1])

If tied items must keep a prior order, stability is required. If not, any order is fine.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Searching a sorted row

Previous Lesson

Searching a sorted row

Next Lesson

Merge sort

Merge sort →