An Order Is a Sign, Not a Magnitude

10 min read

This is the rung above equality, and the last one before Week 1. In 210 you wrote methods that take arguments and return a value. This lesson takes one specific method, the one that answers “which comes first,” and shows you that it has a hidden shape: a set of rules any order must obey, the same rules discrete math gives for an order relation. By the end the never-subtract rule will not be a rule you memorize; it will be the only thing that could possibly be true.

Quick check before you climb (retrieval first)

Answer from memory before reading on. No stakes; retrieving 210 now is what makes the new idea land.

Check yourself. A 210 method returns an int. A caller uses that int in two different ways: it can care about the actual number, or it can care only about whether the number is negative, zero, or positive. Name one method you have seen where only the sign matters.

If you are short on time, here is the floor

You do not need the whole climb to be ready. Walk away with these and you have what this lesson is for.

Bare-minimum takeaways

• The answer to “which comes first” is a sign, not a magnitude: read only negative (before), zero (tie), or positive (after), and ignore how big the number is.
• An order has to obey rules to be an order: reflexive, antisymmetric, and transitive, the order-relation axioms you saw in discrete math.
• The Comparable contract you meet in Week 1 is just those axioms written as a method.
• Do not subtract two ints to compare them. When a field is signed and the two values sit near opposite ends of the int range, a large positive minus a large negative, the subtraction overflows, flips the sign, and makes the order loop, which is a transitivity violation the language never warns you about.
• Use Integer.compare(a, b) everywhere; it decides the sign by comparing, never by subtracting, so it cannot overflow and you never have to track which fields are safe.

What you will be asked

• The Check Yourself quiz is a short misconception check on sign versus magnitude, on why int subtraction overflows and breaks the order, and on writing the Integer.compare fix even for fields that look safe today. The inline self-checks along the way are the same skill in smaller pieces, so doing those is the fastest way to prepare.
• Tuesday builds Comparable directly on this, so the shape of an order is what the lecture assumes you already have.
• Lab 1 rewards the Integer.compare habit on large values, so the habit gets proven general instead of resting on luck with small inputs.

The point

By the end you can say why the answer to “which comes first” is a sign and not a magnitude, you can state the two rules any order must obey and recognize them as the order-relation axioms from discrete math, and you can prove, from the language rulebook, why subtracting two ints to compare them is not a shortcut but a bug. One climb, each rung a click.

The problem (sit with this before reading on)

You want to order students by account balance, who owes the most first, so you reach for the shortest thing that could work:

Comparator<Student> byBalance =
    (a, b) -> a.balanceCents() - b.balanceCents();

A balance is signed: a positive value is money owed, a negative one is a refund the school owes the student. It passes every test you try. Then one night, on two accounts left near opposite ends of the int range by a bad import, the sort lists a large debt below a large refund, an order that is plainly wrong, and only on that pair. The code never changed. The reason it was always capable of this, and only now showed it, is the whole point of this lesson.

Check yourself. The expression is a.balanceCents() - b.balanceCents(). Without knowing the fix yet, name the one thing about int subtraction that could make this return the wrong sign.

Rung 1: the answer is a sign, not a magnitude

Ask “which of these two comes first,” and the smallest honest answer is one of three things: the first comes before the second, they tie, or the first comes after the second. Java packs those three answers into one int and uses only its sign: negative means before, zero means tie, positive means after. The size of the number carries no meaning. A result of -1 and a result of -2000000000 say the identical thing, the first comes before the second.

This is why a comparison is allowed to return any negative number, not just -1. The caller, a sort or a TreeSet, reads the sign and throws the magnitude away. If you ever find yourself caring how big the result is, you have misread the contract.

Collectible insight. An order is a sign, not a magnitude. Trust whether the number is negative, zero, or positive; never trust its size.

Check yourself. A comparison returns -2000000000 for one pair and -1 for another. In one sentence, do those two results tell the caller different things?

Rung 2: an order has a shape, and the shape has rules

An order is not any function that returns a sign. To deserve the name, it has to be consistent with itself. Discrete math gives three axioms for an order relation, and two of them do the visible work here:

• Antisymmetry: if the first does not come after the second and the second does not come after the first, they tie. The order cannot say both come first.
• Transitivity: if the first comes before the second and the second before the third, the first comes before the third. The order cannot loop.

The third axiom, reflexivity, is the quiet one: an item compared with itself ties, so compareTo returns zero. Break antisymmetry or transitivity and a sort cannot finish honestly: it might place an item both ahead of and behind another, or build a cycle with no first element. These rules are not Java’s invention. They are the axioms discrete math gives for an order relation (Rosen, Discrete Mathematics, section 9.6). A sort needs one thing more: every pair has to be comparable, which turns a partial order into a total order. The contract you will sign in Week 1, Comparable, is those axioms written as a method.

Going deeper (optional). In discrete math this is the partial-orderings section (Rosen 9.6), where the same three axioms define a partial order and the comparability requirement promotes it to a total order. The cs-to-math cross-tree link collects that connection.

Collectible insight. The Comparable contract is the order-relation axioms: reflexivity, antisymmetry, and transitivity. You met them in discrete math as the rules of a partial order.

Check yourself. A comparison says a comes before b and b comes before c, but also says c comes before a. Which rule is broken, and why can a sort not finish?

Rung 3: the click, why subtraction is a real bug, not a style choice

Now the opening bug. The language rulebook settles it in two lines. First, the Java Language Specification says an int is a 32-bit two’s-complement value, holding only the range from -2147483648 to 2147483647 (JLS 4.2.1). Second, it says, in these words, that “the integer operators do not indicate overflow or underflow in any way” (JLS 4.2.2). Put those together: when you compute a.balanceCents() - b.balanceCents() and the two values are far enough apart in sign, a large positive minus a large negative, the true result does not fit in 32 bits, so it silently wraps around, and a difference that should be positive comes back negative. Java does not warn you. By the rulebook, it cannot.

A flipped sign is not a small error. It makes the order loop: the comparison can say the first value comes before the second, the second before the third, and the third before the first, the exact cycle from Rung 2. That is a transitivity violation, and a sort handed a cycle has no honest first element to place. On a short list it returns a quietly wrong order; on a longer one the library sort detects the broken contract and throws. (The same flipped sign can also make the order claim both values come first, which breaks antisymmetry.) The math axiom and the language rule describe the same failure from two sides, so the bug is not a Java quirk to work around; it is the order relation breaking its own definition.

The fix removes subtraction entirely:

Comparator<Student> byBalance =
    (a, b) -> Integer.compare(a.balanceCents(), b.balanceCents());

Integer.compare decides the sign by comparing, never by subtracting, so nothing can overflow and the sign is always honest. Not every field is at risk: a count like enrollment is never negative, so subtracting two enrollments could not overflow and would in fact give the right answer. A balance is different, because it is signed, and a large positive minus a large negative is exactly the case that wraps. So the rule is not “this line is broken today,” it is “subtraction is unsafe the moment a field can be negative or approach the ends of the int range, and it corrupts the order with no warning when it does.” You write Integer.compare everywhere so you never have to track which fields are safe. Lab 1 will check this on extreme values, which is how the habit gets proven general instead of merely assumed.

Collectible insight. Subtraction overflow makes the order loop, a transitivity violation, not a Java quirk (and the same flip can break antisymmetry too). The rulebook says the int operators never signal overflow (JLS 4.2.2), so Integer.compare is the only safe sign.

Check yourself. In one sentence that names overflow and transitivity, say why (a, b) -> a.balanceCents() - b.balanceCents() can break a sort.

Rung 4: why Week 1 makes this a contract, not a method

In 210, a method that returned a value was just a method. Week 1 takes the one method that answers “which comes first” and makes it a contract, Comparable, because everything built on top, a TreeSet, a sorted catalog, a binary search, trusts it to obey those axioms. A method that quietly violates the order contract can corrupt a TreeSet far from where the mistake lives, silently dropping an element it mistakes for a duplicate. That is why Week 1 treats the order axioms as law and why this prerequisite ends here, one step below the first lecture, with the shape of an order already in your hands.

Check yourself (competency close). Finish in your own words: “The answer to which comes first is a , not a . An order must be , , and , and subtracting ints to compare can break because ___.”

Check Yourself

Close the notes and answer from memory, then reveal the explanation. Pulling an idea back from memory, and choosing against a tempting wrong answer, is one of the strongest ways to make an idea stick and to catch a misconception before it reaches a graded problem.

What you collected

• An order is a sign, not a magnitude: read negative, zero, or positive, never the size.
• An order must be reflexive, antisymmetric, and transitive, the order-relation axioms from discrete math (Rosen 9.6).
• The Comparable contract is those axioms written as a method.
• Subtraction overflow flips a sign and makes the order loop, a transitivity violation; the rulebook never signals it (JLS 4.2.2), so Integer.compare is the safe form.

Walk into Tuesday with the shape of an order already in hand, so Comparable reads as the contract you expected rather than a new rule to take on faith.