Java sorting: comparators, stability, and ownership

Write the ordering rule as a contract

A shipment report sorts by delivery zone and then by numeric sequence. Comparing only the zone leaves ties equal; adding a sequence makes the intended tie-break visible. Null values need a defined policy before the sort starts.

Do not subtract arbitrary integer or long fields to implement comparison. Arithmetic can overflow and violate ordering. Comparator.comparingInt and thenComparingInt avoid that trap while stating the two rules directly.

A comparator should be antisymmetric in sign and transitive. If the result depends on a mutable clock, changing external state, or side effects, repeated comparisons can disagree. Some sorts detect an invalid contract, but correctness must not depend on an exception catching every bad comparator.

Sorting mutates the chosen container

List.sort changes the list’s order. The program sorts an ArrayList copy so the input encounter order remains available. This is a shallow copy: the Shipment objects themselves are still shared.

Java’s object-list sorting contract is stable, meaning entries equal under the comparator retain their earlier relative order. That does not create a business tie-breaker when the application requires one; define a sequence field for that.

Primitive array sorting, object-array sorting, and collection sorting have different implementation and storage details. Avoid describing every Java sort as one fixed algorithm or one fixed memory budget.

Working program

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

public class ShipmentReportOrder {
    static final class Shipment {
        final int zone;
        final int sequence;
        Shipment(int zone, int sequence) { this.zone = zone; this.sequence = sequence; }
        public String toString() { return zone + ":" + sequence; }
    }
    public static void main(String[] args) {
        List<Shipment> imported = Arrays.asList(new Shipment(2, 7), new Shipment(1, 9), new Shipment(1, 3));
        List<Shipment> sorted = new ArrayList<>(imported);
        sorted.sort(Comparator.comparingInt((Shipment shipment) -> shipment.zone)
                .thenComparingInt(shipment -> shipment.sequence));
        System.out.println(sorted);
        System.out.println(imported);
    }
}

Output

[1:3, 1:9, 2:7]
[2:7, 1:9, 1:3]

Cost and design choices

For the comparison sort used by this list path, budget O(n log n) comparisons in the worst case and O(n) temporary reference space as a conservative upper bound. Copying the list first also requires O(n) references. Comparator cost multiplies the work if comparison itself is expensive.

If only the next highest-priority item is needed repeatedly while arrivals continue, a PriorityQueue may fit better than re-sorting the entire batch after every insertion.

After sorting, the same comparison rule must be used for binary search. A list ordered by zone and sequence is not automatically searchable by a different unrelated field.

Common Mistakes

• Do not mutate ordering fields while a sort is running.
• Do not use subtraction as a comparator.
• Do not assume sorting a shallow copy isolates mutable element state.
• Do not reuse a sorted array with a search comparator that defines another order.