Stability

Beginner Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

A sorter is stable if equal keys maintain their relative order. Insertion Sort is stable; Selection Sort is typically not (depending on the implementation).

Stability matters when additional data is attached to keys.

Where used

Multilevel sorting (first by name, then by grade) and UI tables: stable sorting preserves the previous order. Collections.sort / TimSort are stable; classic Quicksort is typically not.

Depth

A sort is stable if records with the same sort key appear in the same mutual sequence afterward as they did before. This is relevant when multiple sorting steps are combined, such as sorting by first name and then by last name.

Stability is a property of the concrete implementation, not just the algorithm name. Insertion Sort can be stable by only moving strictly larger elements. In contrast, Selection Sort with a wide swap can move an equivalent record over another.

Difficulty levels

Check stability on records with a key and additional identifier.
Make a comparison condition stable or unstable.
Plan multilevel sorts in the correct order.

Pitfalls

Stability cannot be observed with arrays containing entirely different values. A check requires equal keys with distinguishable accompanying data; otherwise, a loss of order remains invisible.

University approvals: 0

Tasks

Question 1

What does stable sorting mean?

It runs in O(1)

Keys remain in the same order.

She doesn't need storage.

She is parallel.

Question 2

Records were first sorted by first name and then stably by last name. What applies within a last name?

The order of the first names from the first step remains unchanged.

The records must appear in reverse input order.

All first names are treated equally.

The first sorting step has no observable effect.

Question 3

Sort the pair objects stably by key. For equal keys, the original order of the ids must be preserved.

Hint

Arrays.sort(T[], Comparator) sorts object arrays in a stable manner. A Comparator can be created using Comparator.comparingInt(p -> p.key).

class Pair {
  final int key;
  final String id;

  Pair(int key, String id) {
    this.key = key;
    this.id = id;
  }
}

class StablePairs {
  static void sort(Pair[] a) {
    // TODO
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithms and Data Structures
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy