Study guide
6.5 Sorting, Comparable, and Comparator
Oracle Java SE 21 Developer 1Z0-830
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Java Basics, Primitive Types, and Operators
1.1 Program Structure, Primitives, Literals, Scopes, and var 1.2 Operators, Precedence, and Type Casting 1.3 Strings, Text Blocks, and StringBuilder 1.4 Date and Time APIs (java.time)
2 Chapter 2: Controlling Program Flow & Pattern Matching
2.1 Conditional Logic: if-else and Ternary Operators 2.2 Switch Statements and Switch Expressions 2.3 Pattern Matching for switch and instanceof 2.4 Loops and Branching Statements
3 Chapter 3: Object-Oriented Design & Class Architecture
3.1 Class Declarations, Constructors, and Object Lifecycle 3.2 Encapsulation and Access Modifiers 3.3 Inheritance, Method Overriding, and Polymorphism 3.4 Abstract Classes and Interfaces 3.5 Nested, Inner, Local, and Anonymous Classes 3.6 Method Overloading, Overload Resolution, and Varargs
4 Chapter 4: Modern Java Data Modeling: Records, Enums, and Sealed Types
4.1 Java Records, Canonical/Compact Constructors, and Component Accessors 4.2 Java Enums: Fields, Methods, and Abstract Constant-Specific Behavior 4.3 Sealed Classes and Interfaces: permits, final, non-sealed, and Hierarchy Architecture 4.4 Advanced Record Patterns (JEP 440), Nested Deconstruction, and Sealed Hierarchy Exhaustiveness
5 Chapter 5: Exception Handling and Annotations
5.1 Exception Hierarchy: Checked vs. Unchecked Exceptions 5.2 Exception Handling: try, catch, finally, and Multi-Catch 5.3 Resource Management: try-with-resources and AutoCloseable 5.4 Custom Exceptions and Best Practices 5.5 Java Annotations: Built-in, Meta-Annotations, and Custom Types
6 Chapter 6: Generics and the Collections Framework
6.1 Generics Fundamentals and Generic Methods 6.2 Wildcards, Type Bounds, and Type Erasure 6.3 Core Collections: Lists, Sets, Queues, and Maps 6.4 Sequenced Collections in Java 21 6.5 Sorting, Comparable, and Comparator 6.6 Arrays: Creation, Multidimensional Forms, and the Arrays Utility Class
7 Chapter 7: Functional Programming & Lambda Expressions
7.1 Built-in Functional Interfaces in java.util.function 7.2 Lambda Expressions, Variable Scopes, and Effectively Final 7.3 Method References: Four Varieties and Edge Cases 7.4 Working with java.util.Optional
8 Chapter 8: The Stream API and Data Pipelines
8.1 Stream Creation and Intermediate Operations 8.2 Terminal Operations and Reductions 8.3 Advanced Collectors, Grouping, Partitioning, and Teeing 8.4 Primitive Streams and Parallel Stream Processing
9 Chapter 9: Concurrency, Multithreading, and Virtual Threads
9.1 Thread Fundamentals, Creation, and Lifecycle 9.2 Thread Safety, Synchronization, and the Java Memory Model 9.3 Concurrency Utilities: ExecutorService, Callable, and Future 9.4 Concurrent Collections, Atomics, and Explicit Locks 9.5 Virtual Threads in Java 21 (Carrier Threads, Pinning, and Best Practices)
10 Chapter 10: The Java Platform Module System (JPMS)
10.1 Module Architecture and module-info.java Declarations 10.2 Module Directives: requires, exports, opens, provides, and uses 10.3 Modular Compilation, Packaging, and CLI Execution 10.4 Module Types, Migration Strategies, ServiceLoader SPI, and JLink
11 Chapter 11: Java I/O, NIO.2, and Object Serialization
11.1 Classic Java I/O Streams and Readers/Writers 11.2 Java NIO.2 File API: Path, Paths, and File System Operations 11.3 Advanced NIO.2 Stream Operations and Directory Traversal 11.4 Java Object Serialization and Record Serialization
12 Chapter 12: Implementing Localization and Internationalization
12.1 Locales and Resource Bundles 12.2 Formatting and Parsing Numbers, Currencies, Dates, Times, and Messages
6.5 Sorting, Comparable, and Comparator
Key Takeaways Explain This Topic AI
Comparable<T> defines the natural ordering of a class via int compareTo(T o), returning negative, zero, or positive integer values.
Comparator<T> defines customizable external sorting strategies via compare(T o1, T o2) and supports rich composition with comparing, thenComparing, and reversed.
Collections.binarySearch and Arrays.binarySearch require collections/arrays to be pre-sorted according to the searching comparator; otherwise, search results are undefined.
Binary search returns the non-negative index if found, or (-(insertion point) - 1) if absent, allowing exact deduction of where the searched element belongs.
Direct integer subtraction (o1.val - o2.val) in comparators is an anti-pattern prone to integer overflow; always use Integer.compare(a, b).
Last updated: September 2026
Sorting, Comparable, and Comparator
Sorting, ordering, and binary searching are core capabilities of the Java platform. The Oracle Certified Professional: Java SE 21 Developer (1Z0-830) exam tests your understanding of natural ordering with Comparable , flexible multi-criteria sorting using Comparator factory and chaining methods, in-place sorting APIs, and the exact return value contract of Collections.binarySearch and Arrays.binarySearch .
1. Natural Ordering with Comparable<T>
The java.lang.Comparable<T> interface imposes a natural ordering on the objects of each class that implements it. package java.lang;
- public interface Comparable<T> {
- int compareTo(T o);
- }
- The compareTo Contract
Returns a negative integer if this < o .
Returns zero ( 0 ) if this is equal to o .
Returns a positive integer if this > o .
Symmetry : sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) .
Transitivity : If x.compareTo(y) > 0 and y.compareTo(z) > 0 , then x.compareTo(z) > 0 .
Null Handling : Must throw NullPointerException if o is null . public record Employee(int id, String name, double salary) implements Comparable<Employee> {
- @Override
- public int compareTo(Employee other) {
- // Safe integer comparison avoiding arithmetic overflow
- return Integer.compare(this.id, other.id);
- }
- }
- Consistency with equals
A natural ordering is said to be consistent with equals if and only if: ( x . compareTo ( y ) = = 0 ) ⟺ ( x . equals ( y ) ) (x.\text{compareTo}(y) == 0) \iff (x.\text{equals}(y)) ( x . compareTo ( y ) == 0 ) ⟺ ( x . equals ( y ))
While not strictly required by the compiler, violating this rule creates unexpected behavior in sorted collections ( TreeSet , TreeMap ) which rely exclusively on compareTo rather than equals to determine element uniqueness: // BigDecimal: compareTo checks numeric value, equals checks numeric value AND scale!
- BigDecimal d1 = new BigDecimal("2.0");
- BigDecimal d2 = new BigDecimal("2.00");
- Set<BigDecimal> hashSet = new HashSet<>();
- hashSet.add(d1); hashSet.add(d2); // size = 2 (d1.equals(d2) is false)
- Set<BigDecimal> treeSet = new TreeSet<>();
- treeSet.add(d1); treeSet.add(d2); // size = 1 (d1.compareTo(d2) == 0 -> considered duplicate!)
- 2. Custom Ordering with Comparator<T>
The java.util.Comparator<T> functional interface enables custom sorting logic external to the class definition: @FunctionalInterface
- public interface Comparator<T> {
- int compare(T o1, T o2);
- }
- Static Factory Methods on Comparator
Java provides static helper methods to construct comparators declaratively:
- Factory Method Description
- Comparator.naturalOrder() Sorts according to natural Comparable order
- Comparator.reverseOrder() Sorts in reverse of natural order
- Comparator.comparing(keyExtractor) Extracts a Comparable sort key (e.g., Employee::name )
- Comparator.comparing(keyExtractor, keyComp) Extracts key and compares using custom comparator
- Comparator.comparingInt(toIntFunc) Extracts primitive int to avoid autoboxing overhead
- Comparator.comparingLong(toLongFunc) Extracts primitive long
- Comparator.comparingDouble(toDoubleFunc) Extracts primitive double
- Comparator.nullsFirst(comp) Places null elements at the beginning
- Comparator.nullsLast(comp) Places null elements at the end
- 3. Comparator Chaining and Combinator Methods
Complex multi-tier sorting criteria can be composed cleanly using default methods on Comparator : // Multi-level sort: Sort by Department ASC, then by Salary DESC, then by Name ASC
- Comparator<Employee> comp = Comparator
- .comparing(Employee::department)
- .thenComparing(Comparator.comparingDouble(Employee::salary).reversed())
- .thenComparing(Employee::name);
- List<Employee> staff = getEmployees();
- staff.sort(comp); // In-place sort using List.sort
- Precedence and the .reversed() Placement Trap
The .reversed() method inverts the comparator instance on which it is called. Its placement in a chain dramatically affects the sorting order: // Trap 1: reversed() at the end inverts the ENTIRE composite comparator!
- Comparator<Employee> c1 = Comparator.comparing(Employee::department)
- .thenComparing(Employee::salary)
- .reversed();
- // Result: Department DESC, then Salary DESC
- // Trap 2: reversed() attached to the first comparator inverts ONLY that tier
- Comparator<Employee> c2 = Comparator.comparing(Employee::department)
- .reversed()
- .thenComparing(Employee::salary);
- // Result: Department DESC, then Salary ASC
- Null-Safe Sorting
When collections contain null elements, using a plain comparator throws NullPointerException . Wrap the comparator with nullsFirst or nullsLast : // Sort names alphabetically, placing null entries at the very end
Comparator<String> safeComp = Comparator.nullsLast(Comparator.naturalOrder());
- List<String> names = new ArrayList<>(Arrays.asList("Charlie", null, "Alice", "Bob"));
- names.sort(safeComp);
- System.out.println(names); // [Alice, Bob, Charlie, null]
- 4. Sorting APIs in Modern Java
API Method Target In-Place? Null Comparator Meaning Sorting Algorithm
list.sort(comparator) List<E> Yes Uses natural ordering ( Comparable ) Timsort (Stable, O ( n log n ) O(n \log n) O ( n lo g n ) )
- Collections.sort(list) List<T extends Comparable> Yes Uses natural ordering Timsort
- Collections.sort(list, comp) List<T> Yes Uses custom Comparator Timsort
- Arrays.sort(array) T[] (Objects) Yes Uses natural ordering Timsort (Stable)
- Arrays.sort(primitiveArray) Primitives ( int[] , etc.) Yes N/A Dual-Pivot Quicksort (Unstable)
- Arrays.parallelSort(array) T[] or Primitives Yes Natural or Custom Parallel Merge-Sort
- 5. Searching Sorted Collections: binarySearch
Collections.binarySearch and Arrays.binarySearch perform fast O ( log n ) O(\log n) O ( lo g n ) searches on sorted datasets.
Mandatory Preconditions
The collection/array MUST be sorted in ascending order prior to calling binarySearch .
If sorted using a custom Comparator , the exact same comparator must be passed to binarySearch(list, key, comparator) .
If the list is unsorted or sorted in reverse without passing the reverse comparator, the return value is undefined .
If searching a LinkedList , binarySearch degrades to O ( n ) O(n) O ( n ) time due to sequential node traversal.
Return Value Mathematical Formula
Key Found : Returns the index ( i ≥ 0 i \ge 0 i ≥ 0 ) of the search key. If multiple matching elements exist, which matching index is returned is not guaranteed.
Key Not Found : Returns a negative integer : Return Value = − ( insertion point ) − 1 \text{Return Value} = -(\text{insertion point}) - 1 Return Value = − ( insertion point ) − 1
Insertion Point Definition : The index of the first element greater than the search key, or list.size() if all elements in the list are smaller than the search key.
Deducing Insertion Point from Return Value : Insertion Point = − ( Return Value + 1 ) \text{Insertion Point} = -(\text{Return Value} + 1) Insertion Point = − ( Return Value + 1 ) List<Integer> list = List.of(10, 20, 30, 50, 60);
- // Search for 30 (Present at index 2)
- int idx1 = Collections.binarySearch(list, 30); // returns 2
- // Search for 40 (Absent; would be inserted at index 3)
- // Formula: -(3) - 1 = -4
- int idx2 = Collections.binarySearch(list, 40); // returns -4
- // Search for 5 (Absent; would be inserted at index 0)
- // Formula: -(0) - 1 = -1
- int idx3 = Collections.binarySearch(list, 5); // returns -1
- // Search for 100 (Absent; would be inserted at index 5)
- // Formula: -(5) - 1 = -6
- int idx4 = Collections.binarySearch(list, 100);// returns -6
- 6. Common Sorting Pitfalls and Anti-Patterns
- 1. Integer Subtraction Overflow Anti-Pattern
Writing a comparator using raw arithmetic subtraction: // DANGEROUS ANTI-PATTERN!
Comparator<Integer> badComp = (a, b) -> a - b;
If a = Integer.MIN_VALUE ( − 2 , 147 , 483 , 648 -2,147,483,648 − 2 , 147 , 483 , 648 ) and b = 1 , a - b overflows to + 2 , 147 , 483 , 647 +2,147,483,647 + 2 , 147 , 483 , 647 (positive!), falsely indicating that a > b a > b a > b . Always use Integer.compare(a, b) .
2. Modifying Sort Keys of Elements in TreeSet / TreeMap
If an object is added to a TreeSet and its sort key field is subsequently modified, the tree's internal ordering invariants are corrupted. The collection can no longer find or remove the modified element, leading to severe memory leaks and data corruption.