Middle · Algorithms

A comparator using <= and an unstable tie break

A sort comparator returns a.Priority <= b.Priority. Equal-priority items reorder unpredictably. Which contracts must be fixed?

Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.

EXAMPLE · FRAGMENT UNLESS A COMPLETE PROGRAM IS SHOWN

package main

import (
	"fmt"
	"sort"
)

type Job struct {
	Name     string
	Priority int
}

func main() {
	jobs := []Job{{"first", 2}, {"second", 1}, {"third", 2}}
	sort.SliceStable(jobs, func(i, j int) bool { return jobs[i].Priority < jobs[j].Priority })
	fmt.Println(jobs) // second, first, third
}

Reveal a strong answer

A comparator must establish a strict weak ordering. In particular, an item is not less than itself. Using <= violates this contract for equal keys, and a comparator that depends on changing external state can violate it while sorting. Define all tie semantics before choosing an implementation.
A stable sort preserves input order among items the comparator considers equal; it does not invent a global order for data that arrived nondeterministically. Add an explicit stable secondary key if different processes must produce the same total result from differently ordered inputs.
Sorting mutates the slice being sorted and can affect aliases to its backing storage. Copy deliberately if the caller retains the original order. For floating-point inputs, specify how NaN and signed zero fit the ordering rather than assuming ordinary < comparisons define every desired relation. Test equal keys, empty data, already sorted data and adversarial boundaries.

Common trap

Stable sorting cannot repair an invalid comparator or make nondeterministic input order a deterministic business tie break.

Complexity & use

For the documented stable-sort implementation: O(n log n) comparisons and O(n log² n) swaps; comparator cost and payload movement also matter.

Try it

Fix the comparator, predict the order of equal-priority jobs and decide whether the input backing array may be mutated.

Worked solution

Compare priority with <, then either use stable sorting to preserve a meaningful existing order or compare an explicit secondary key. Test irreflexivity and consistency over representative triples, not just one happy output. Use the implementation’s documented comparison/move costs and benchmark expensive payload movement if that matters.

Change the constraint

Would the same stable sort produce identical results if each replica initially received equal-priority items in a different order?

How did you do?

Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.

Not marked. Progress stays on this browser, separate from course completion.

Primary references

Checked 2026-10-28. Use documentation for your pinned runtime, driver and tool version.