Equality and Object Identity

Sorting requires a defined comparison, because there is no natural ascending order for arbitrary objects.

Programming

Interactive lab

Try it: Sorting with key= and reverse=

How sorted() and list.sort() compute key(item) once per item, order the items by those keys with Python's comparison rules, and keep equal keys in their original order — including py4e's sort-a-dict-by-value pattern.

How it works

Decorate: call the key function once on every item (no key means the item itself is compared).
Compare keys with Python's rules: ints by value, strs by code point ('Z' < 'a'), tuples item by item.
Order the items by key; reverse=True puts the largest key first.
Stable: items with equal keys keep their original relative order, also with reverse=True.
sorted() returns a new list; list.sort() rearranges the list in place and returns None; [:N] keeps the first N.

Default run (12 steps): 5 items in their original order. Python will call lambda t: t[1] once per item. … sorted() returned a new list: result = [('fig', 5), ('kiwi', 5), ('pear', 3), ('apple', 3), ('date', 1)].

Simplified: Up to 10 items of one kind (ints, short ASCII words, (word, count) tuples or a small dict) and a fixed menu of key functions. The sorting algorithm itself (Timsort) is not shown — only what it guarantees: the order by key and stability.

Educational simulation

Loading the simulation…

Why Sorting Needs a Rule

Put a list of numbers or a list of strings into a program and ask it to sort them, and the result is obvious to you: numbers go from smallest to largest, and strings go in alphabetical order. The program can do this because it already knows how to decide that one number or one string comes before another. Custom objects are different. A program that holds a list of your own objects has no built-in idea of which object should come first.

Sorting means arranging items in ascending order according to some criterion. For custom objects there is no built-in criterion, so something must be defined for comparing them before any ordering is possible. This article follows one question through the whole topic: when a sort puts one object before another, where did that decision come from?

Reading compareTo Return Values

The Comparable interface is a parameterized interface, written Comparable<T>, that expresses the ability to be compared to an object of type T. It defines exactly one method, compareTo, which takes an object of type T as its parameter. Calling obj1.compareTo(obj2) asks obj1 to report where it stands relative to obj2.

Only the sign of the result matters. A negative result means obj1 comes before obj2. A positive result means obj1 comes after obj2. A zero result means the two objects are the same for this comparison. The actual size of the number carries no meaning, so a return value of -1 and a return value of -250 both say that the first object comes before the second.

Return value	Meaning for obj1.compareTo(obj2)	Position in sorted order
Negative	obj1 comes before obj2	obj1 is placed earlier
Zero	The two count as the same for this comparison	Neither is required to come first
Positive	obj1 comes after obj2	obj1 is placed later

Reading the sign of a compareTo result

What do you think happens?

Given a class whose compareTo puts objects in alphabetical order by name, what sign does ben.compareTo(ana) return if ben's name is Ben and ana's name is Ana, and what does that sign say about their order?

Negative, so Ben comes before Ana
Positive, so Ben comes before Ana
Zero, so Ben and Ana are equal

Reveal answer

Answer:

Negative, so Ben comes before Ana

Ben is compared to Ana by name, and Ben would come before Ana in alphabetical order only if its comparison returns a negative value. Negative means the calling object comes first.

Building a Natural Order with Comparable

The source develops a class called FullName, which holds a first name and a last name. Both fields are required to be non-null. To make FullName objects sortable, the class declares that it implements Comparable<FullName> and defines compareTo so that the last name is the primary key. Only when two last names match does the first name decide the order.

java

import java.util.Objects;

public class FullName implements Comparable<FullName> {
    private final String first;
    private final String last;

    public FullName(String first, String last) {
        this.first = Objects.requireNonNull(first);
        this.last = Objects.requireNonNull(last);
    }

    @Override
    public int compareTo(FullName other) {
        if (!last.equals(other.last)) {
            return last.compareTo(other.last) < 0 ? -1 : 1;
        }
        return first.compareTo(other.first);
    }
}

import java.util.Objects;

public class FullName implements Comparable<FullName> {
    private final String first;
    private final String last;

    public FullName(String first, String last) {
        this.first = Objects.requireNonNull(first);
        this.last = Objects.requireNonNull(last);
    }

    @Override
    public int compareTo(FullName other) {
        if (!last.equals(other.last)) {
            return last.compareTo(other.last) < 0 ? -1 : 1;
        }
        return first.compareTo(other.first);
    }
}

Notes on the code

implements Comparable<FullName> declares the natural order and fixes the type that compareTo accepts
The last-name check runs first, so last name is the primary key
Only when the last names match does the first-name comparison decide the result

The method returns -1 or 1 when the last names differ, and it returns the first-name comparison result when they match. Both forms satisfy the contract because only the sign matters. The source also notes that the same compareTo convention applies when the class is written as a record class, since record classes can implement interfaces too.

Tracing a Sort Through compareTo

The approach here is to run comparisons and watch what they return, then work backward to the rule that produces each result. Take three FullName objects in this input order: Ana Smith, Ben Adams, and Carla Smith. Before reading the worked steps, predict which object a sort should place first and what sign each comparison should return.

Worked example

Sorting Three Names by Last Name, Then First Name

Sort the list [Ana Smith, Ben Adams, Carla Smith] using the compareTo defined in FullName.

1
Compare Ben Adams with Ana Smith
The last names are Adams and Smith, which differ. Adams compared with Smith is negative, so the method returns -1. Ben comes before Ana.
2
Compare Ana Smith with Carla Smith
The last names are both Smith, so the method moves on. The first names are Ana and Carla. Ana compared with Carla is negative, so the method returns that negative result. Ana comes before Carla.
3
Assemble the sorted order
Ben Adams comes first because his last name is earliest. Ana Smith comes before Carla Smith because the last names tie and the first name decides.

Result

Ben Adams, Ana Smith, Carla Smith

Which pair of elements gets compared at each step, and how does each returned sign decide the placement? The sort routine asks one object to compare itself with another, and the sign of the reply sets the order.

Notice that the sort never asks which of the three objects is better in some general sense. It only asks pairwise questions, and each answer is a sign. The arrangement that the program ends up with is the result of many such small answers.

Keeping equals and compareTo in Agreement

A class that implements Comparable should try to make equals and compareTo agree. The goal is that obj1.equals(obj2) and obj1.compareTo(obj2) == 0 always have the same truth value. In the FullName example, equals compares both first and last names, and compareTo compares last names and then first names, so the two notions match.

Comparators Outside the Class

Comparable puts the comparison inside the class. A Comparator takes a different approach: it is a separate object whose job is to compare two objects of some type T. The object must implement Comparator<T>, and the interface defines one method, compare(T obj1, T obj2). Its return value follows the same sign convention as compareTo: a negative result means obj1 comes before obj2, a positive result means obj1 comes after obj2, and zero means the two count as the same for this comparison.

How is the Comparator object related to the class whose instances it compares? The Comparator is a separate object that holds the comparison logic and receives two instances of the class as inputs.

Comparators are useful in two situations. The first is comparing objects whose class does not implement Comparable, such as a class you cannot modify. The second is defining several different orderings over the same collection of objects. Because Comparator is a functional interface, comparators are often written as lambda expressions.

java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

record Address(String street, String zip) { }

Comparator<Address> byZip = (a, b) -> a.zip().compareTo(b.zip());

List<Address> addresses = new ArrayList<>();
addresses.add(new Address("12 Oak Lane", "30301"));
addresses.add(new Address("4 Pine Road", "10001"));
addresses.add(new Address("9 Elm Street", "30301"));

addresses.sort(byZip);

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

record Address(String street, String zip) { }

Comparator<Address> byZip = (a, b) -> a.zip().compareTo(b.zip());

List<Address> addresses = new ArrayList<>();
addresses.add(new Address("12 Oak Lane", "30301"));
addresses.add(new Address("4 Pine Road", "10001"));
addresses.add(new Address("9 Elm Street", "30301"));

addresses.sort(byZip);

Output

Addresses ordered by zip: 10001 (4 Pine Road), then the two 30301 entries in their original relative order

Notes on the code

Address does not implement Comparable, so the ordering must come from outside the class
The lambda is the Comparator; it receives two Address objects and returns a sign
Passing byZip to sort uses the external comparison instead of any compareTo in Address

Because this comparator looks only at the zip code, it reports zero for any two addresses that share a zip code, even when they differ in every other field. The source describes this as a deliberate choice for the ordering, not a mistake. The comparator has no claim to decide whether two addresses are equal.

Choosing Between Comparable and Comparator

Situation	Comparable<T>	Comparator<T>
Where the comparison lives	Inside the class, in compareTo	In a separate object, in compare(obj1, obj2)
Class can be modified	Yes, it can implement Comparable	Not required; works even when you cannot edit the class
Number of orderings	One natural order for the class	Several different orderings over the same objects
Typical form	A class declaration with compareTo	A class or lambda implementing compare
Agreement with equals	Should be kept consistent with equals	Need not agree with equals (zip-code example)

Choosing the right comparison mechanism

A useful rule of thumb follows from the source: if the class has one ordering that naturally belongs to it, make it Comparable. If the class cannot be changed, or if you need to sort the same objects in more than one way, use a Comparator.

Finding Where an Unexpected Order Comes From

When a sorted list looks wrong, the cause is almost always a single branch inside the comparison logic. The method is a sequence of decisions, so you can trace it the same way you traced the sort: pick the pair of objects that ended up in the wrong place, then follow the path through the method until you find the branch that returns the sign you did not expect.

Following the decision path inside compareTo for a given pair, at which branch does the result go the wrong way? The last-name check decides the result whenever the last names differ, so a wrong order often starts there.

Common mistake
Assuming the size of the returned number carries meaning
What it looks like
Expecting compareTo to return -5 for a bigger gap than -1 and treating that as a stronger ordering
Why it fails
Only the sign of the result matters, so both values say the same thing about order
Do this instead
Read the sign alone when deciding which object comes first
Common mistake
Treating a zero result as proof that two objects are equal everywhere
What it looks like
Two addresses with the same zip code compare as zero under a zip-only comparator
Why it fails
Zero means the two count as the same for that comparison only
Do this instead
Check equals separately when you need true equality, and keep equals and compareTo in agreement inside Comparable classes
Common mistake
Looking for the wrong branch when the order looks off
What it looks like
Debugging the first-name code when two people with different last names are out of place
Why it fails
The last-name check returns first, so the first-name branch is never reached for that pair
Do this instead
Trace the pair through the decision path and find the branch that actually returned the result
Common mistake
Calling sort on a list of custom objects without a Comparable class or a Comparator

Practice Tracing a Comparison

MEDIUM

Using the FullName class from this article, predict the result of each call: first, new FullName("Carla", "Smith").compareTo(new FullName("Ana", "Smith")); second, new FullName("Zoe", "Adams").compareTo(new FullName("Ana", "Smith")). For each, say whether the sign is negative, zero, or positive and explain which branch of compareTo produced it.

Hints

Start with the last-name check. Are the last names equal in the first call?
In the second call, compare Adams with Smith before looking at any first names.
A positive result means the calling object comes after the other one.

Your attempt (not saved)