Stable Sort and the Two-Pass Trick

Before You Start

Check each box you can do from memory. A box you cannot check yet is not a problem; it points you to a quick refresher, not a grade.

• I can call Arrays.sort with a Comparator on an object array and explain what the sort guarantees about equal elements.
• I can call list.sort with a Comparator on an ArrayList and describe how it differs from the primitive-array overload.
• I can state in one sentence what “stable sort” means without looking it up.

Try This First

Six players: three from “Bears,” three from “Aces.” Across both teams, games played are 5, 10, 15, 8, 12, 20.

// Pass 1
players.sort(byGamesPlayed);   // ascending games played

// Pass 2
players.sort(byTeam);          // alphabetical by team

Before reading further: predict the final order. Which team appears first? Within each team, what order?

What You Need To Walk In With

The Insight: A stable sort preserves the previous ordering among elements the new comparator considers equal. This means: sort by the least important key first, most important key last. After the final sort, all elements are in primary-key order. Within each primary-key group, the stable property keeps them in secondary-key order from the previous sort. The insight is that “least first” is backwards from how most people think, which is why this is one of the most commonly confused sorting idioms.

A memory anchor that many people find helpful: think of the final sort as the “boss.” The boss has last say on the overall order. Every previous sort sets up a detail ordering that the boss preserves among elements it considers equal. The boss does not care about details among equals, so whatever order the earlier sort left them in, stability keeps it.

You can: state what stable means and cite Java’s guarantee for object-array sorts; apply the two-pass trick to sort by two keys; translate a two-pass sort into a single thenComparing chain; and explain from first principles why the secondary key must run first.

How It Works

Stability: the formal definition

A sort algorithm is stable when elements that are equal under the comparator maintain their original relative order. After a stable sort, if element a preceded element b in the input, and compare(a, b) == 0, then a still precedes b in the output.

Java’s guarantees (from the Java 25 Arrays.sort API):

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

This applies to Arrays.sort(T[], Comparator) and Collections.sort/list.sort. It does NOT apply to Arrays.sort(int[]) and other primitive-array overloads, which use a different algorithm.

The two-pass trick: secondary before primary

To sort by team (primary) then by games played within each team (secondary):

players.sort(byGamesPlayed);   // secondary key: sort by games played ascending
players.sort(byTeam);          // primary key: sort by team alphabetically

Why secondary first:

After the first sort, players are in games-played order globally. After the second sort:

• Players are grouped by team.
• Within each team group, the team comparator returns 0 for all members, so their relative order is unchanged.
• “Unchanged” means they remain in the order they were in at the start of the second sort: games-played ascending.

The primary sort dominates the outer order. The stable property preserves the secondary order within each primary group.

Quick check

The modern alternative: thenComparing

The two-pass trick requires two full sorts. The modern idiom composes both keys into one comparator:

players.sort(byTeam.thenComparing(byGamesPlayed));

This is a single pass. It sorts by team first, then by games played as a tiebreaker. The result is identical to the two-pass trick and is the preferred form for new code. Multi-key ordering with thenComparing covers this in depth.

Worked Example: Predict Then Check

Initial list:

players.sort(byGamesPlayed);   // ascending games played
players.sort(byTeam);          // alphabetical by team

Predict the final order (team, then within team).

players.sort(byTeam.thenComparing(byGamesPlayed));

Common Misconceptions

Misconception 1: sorting by primary key first in a two-pass scheme

Wrong mental model: “Sort by team first, then by games played: the team grouping will persist.”

Why it breaks: The second sort (by games played) is the dominant sort. After it runs, elements are ordered globally by games played, not by team. The first sort’s team grouping is destroyed by the second pass wherever games-played values differ across teams.

How to correct: In the two-pass trick, secondary key first, primary key last. Or use thenComparing to avoid the trap entirely.

Misconception 2: assuming Arrays.sort(int[]) is stable

Wrong mental model: “All Java sort methods are documented as stable.”

Why it matters: Arrays.sort(int[]) uses dual-pivot quicksort, which is not stable. For primitive arrays, this rarely matters in practice (there is no “identity” to preserve for primitive values). But when students design a two-pass trick on a boxed Integer[], they need the object-array overload, not the primitive overload.

How to correct: Use Integer[] (object array) or List<Integer> when stability matters. Verify the stability guarantee from the javadoc for the specific overload.

Source: Java 25 Arrays.sort for int arrays javadoc (no stability guarantee mentioned).

Quick check

Formal Definition and Interface Contract

From the Java 25 Arrays.sort API:

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

From the Java 25 Collections.sort API:

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

Both use TimSort (introduced in Java 7), which achieves O(n log n) worst-case while maintaining stability.

Mental Model

Think of the two-pass trick as writing in pencil first, then in ink. Pass 1 writes the secondary ordering in pencil. Pass 2 writes the primary ordering in ink over the whole list. Where the ink says two elements are equal, the pencil order underneath is preserved (because the stable sort does not erase pencil when the ink says “same”). Where the ink says two elements differ, the ink dominates.

Connections

Within CSCD 210/211: The stable-sort guarantee of Arrays.sort was mentioned in passing in Arrays.sort with a Comparator. This lesson unpacks why stability matters and how it enables the two-pass trick.

Looking back: list.sort with a Comparator covered the sort call. This lesson covers a property of that sort that enables a specific multi-key idiom.

Looking ahead: Multi-key ordering with thenComparing covers thenComparing, which replaces the two-pass trick with a single composed comparator. That is the modern approach for all new code.

Practice

Level 1

Sort ArrayList<Player> players by last name (secondary), then by team (primary), using two passes. Write both sort calls.

players.sort(Comparator.comparing(Player::getLastName));  // secondary key first
players.sort(Comparator.comparing(Player::getTeam));      // primary key last

Level 2

Rewrite the two-pass sort from Level 1 as a single list.sort call using thenComparing.

players.sort(Comparator.comparing(Player::getTeam)
                       .thenComparing(Player::getLastName));

Level 3

Explain in 4-5 sentences why the secondary key must be sorted first in the two-pass trick, referencing the definition of stability. Then give a concrete counter-example showing what happens when the order is reversed.

Go Deeper (optional)

This depth is not needed to write correct sorting code. Read on only if you are curious about where this fits in the bigger picture.

The two-pass trick shows up throughout professional codebases, particularly in code written before Java 8 introduced thenComparing. Reading legacy code and recognizing the pattern, then confidently suggesting a thenComparing replacement, is a concrete skill that appears in code reviews at every level of seniority.

Stability is also a genuine algorithmic property with a real history. Merge sort is inherently stable: its merge step always picks the left element when two elements are equal, preserving their relative order by construction. Quicksort is not inherently stable: its partition step can move an element past another equal element. TimSort, which Java uses for object-array sorts since Java 7, is a hybrid of insertion sort and merge sort, designed by Tim Peters to exploit the natural runs that appear in real-world data. The stability of TimSort comes from the merge-sort half of its design. This is why the primitive-array overload Arrays.sort(int[]) uses dual-pivot quicksort (fast, not documented as stable) while the object-array overload Arrays.sort(T[], Comparator) uses TimSort (stable, and fast on typical data).

If you continue into algorithms or systems work, you will see stability reappear as a design constraint: database sort operators, spreadsheet sort dialogs, and distributed data pipelines all depend on it in different ways. The core principle is always the same: when the ordering criterion says two things are equal, which one gets to keep its position?

Check Yourself

Close the notes and answer each one from memory, then reveal it. Pulling an idea back from memory is one of the strongest ways to make it stick.