1.23 Stability and Determinism

Stability and determinism describe how predictably an algorithm behaves when there are ties, repeated values, or multiple valid answers. These properties do not always change the mathematical objective, but they often change the required output, the implementation, and the tests.

An algorithm is deterministic if the same input always produces the same output. An algorithm is stable, in the common sorting sense, if equal keys keep their original relative order. More broadly, stability means that small or irrelevant differences in representation do not cause surprising changes in the output.

Problem

You have a problem with repeated values, equal priorities, or multiple valid answers, and you need to define which answer the algorithm should return.

Solution

State the tie-breaking rule explicitly.

Use this template:

Output:
  Return a valid answer satisfying the objective.

Tie-breaking:
  If multiple answers are valid, return the one with:
    smallest index
    earliest occurrence
    lexicographically smallest order
    original relative order
    deterministic priority order

If no tie-breaking is required, say so:

Any valid answer is acceptable.

This gives the implementation more freedom.

Example: Maximum Index

Problem:

Given an array A, return an index of a maximum value.

If the input is:

[4, 7, 7, 3]

then both index 1 and index 2 are valid unless the problem says otherwise.

First maximum:

best = 0

for i = 1 to n - 1:
  if A[i] > A[best]:
    best = i

return best

Last maximum:

best = 0

for i = 1 to n - 1:
  if A[i] >= A[best]:
    best = i

return best

The only difference is the comparison operator. That small difference encodes the tie-breaking rule.

Example: Stable Sorting

Suppose records have a key and an original position.

[(key=2, name=A), (key=1, name=B), (key=2, name=C)]

A stable sort by key returns:

[(key=1, name=B), (key=2, name=A), (key=2, name=C)]

The two records with key 2 remain in their original order.

An unstable sort may return:

[(key=1, name=B), (key=2, name=C), (key=2, name=A)]

Both outputs are sorted by key, but only the first preserves relative order among equal keys.

Stability matters when sorting happens in stages. For example, to sort people by last name and then by first name, one common method is:

stable sort by first name
stable sort by last name

The second stable sort preserves the first-name order inside each last-name group.

Determinism in Graph Algorithms

Graph traversal often has many valid orders. A depth-first search depends on neighbor order.

If adjacency lists are stored as:

0: [1, 2]

DFS may visit 1 before 2.

If stored as:

0: [2, 1]

DFS may visit 2 before 1.

Both may be correct for reachability, but they produce different traversal orders and different DFS trees.

To make output deterministic, sort neighbors or define a fixed iteration order:

for each neighbor u of v in increasing label order:
  visit u

This may add cost, so it should be a deliberate choice.

Determinism in Priority Queues

Priority queues often have unspecified behavior when priorities are equal. If two tasks have the same priority, the extracted order may depend on internal heap layout.

To make behavior deterministic, use a composite key:

(priority, insertion_order)

or:

(distance, vertex_id)

For Dijkstra’s algorithm, the shortest distance values may tie. If the final distance array is the only output, tie order usually does not matter. If the output includes a shortest-path tree, tie-breaking changes which valid tree is returned.

Randomized Algorithms

Randomized algorithms are intentionally nondeterministic unless the random seed is fixed.

For testing, use a fixed seed:

seed = 12345

For production, randomized seeds may be acceptable or even desirable. The contract should distinguish between:

same input, same seed -> same output

and:

same input, different seeds -> possibly different valid outputs

Reproducibility

Determinism supports reproducibility. This matters when:

tests compare exact outputs
debugging depends on replaying a failure
distributed jobs must produce identical results
cached results depend on output identity

If reproducibility matters, avoid depending on unspecified iteration order, hash map traversal order, thread scheduling, or random seeds that are not recorded.

Common Pitfalls

Do not assume “any valid answer” when the tests expect a specific one.

Do not use unstable sorting when later logic depends on the order of equal keys.

Do not rely on hash map iteration order for deterministic output.

Do not forget that parallel algorithms may produce valid but different orders unless synchronization or tie-breaking is specified.

Do not add deterministic sorting without accounting for its cost.

Takeaway

Stability and determinism turn “a correct answer” into “the expected correct answer.” State tie-breaking rules, preserve order when required, and avoid relying on unspecified behavior. When many outputs are valid, either define the exact one you want or write tests that accept all valid answers.