Java Sort and Custom Comparators: The Coding Interview Guide

You're 20 minutes into the interview, your comparator looks reasonable, and the interviewer says "looks good, what's the time complexity?" Then you realize you wrote (a, b) -> a - b and there's an Integer.MAX_VALUE in the test case. Congratulations. Your sort just returned garbage without saying a word about it.

Java's sort API looks like a two-line thing until it isn't. This guide covers all the ways it bites you.

Two Different Algorithms Are Hiding Inside `Arrays.sort`

Java picks its sorting algorithm based on the type you hand it, and it does not tell you it's doing this. Pass a primitive array and you get dual-pivot quicksort. Pass an object array and you get Timsort. Different algorithms, different stability guarantees, different rules.

Dual-pivot quicksort (introduced in Java 7 by Vladimir Yaroslavskiy) carves the array into three regions using two pivots. Faster in practice than single-pivot for typical input, O(n log n) average. Not stable. For primitives that's completely fine: two ints with the same value are identical, so stability is meaningless.

Timsort is a hybrid merge sort tuned for real-world data that already has partial order. Stable, O(n log n) worst case, and what Java uses for all object arrays. That includes Integer[], String[], any custom class, and anything living inside a List.

int[] nums = {3, 1, 2};
Arrays.sort(nums);            // dual-pivot quicksort, in-place, no comparator allowed

Integer[] boxed = {3, 1, 2};
Arrays.sort(boxed);           // Timsort, stable

List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 2));
Collections.sort(list);       // Timsort, stable, delegates to List.sort internally
list.sort(null);              // same thing, null means natural order

Method	Input type	Algorithm	Stable	Accepts comparator
`Arrays.sort(int[])`	primitive	dual-pivot quicksort	No	No
`Arrays.sort(T[])`	object	Timsort	Yes	Yes (optional)
`Collections.sort(List<T>)`	List	Timsort	Yes	Yes (optional)
`list.sort(comp)`	List	Timsort	Yes	Yes

You Cannot Pass a Comparator to a Primitive Array

This is the one candidates discover at exactly the wrong moment. There is no Arrays.sort(int[], Comparator) overload. Primitive types don't participate in generics. When you need a sorted int[] in reverse, you have three exits.

int[] nums = {5, 1, 4, 2};

// Option 1: box it (most readable)
Integer[] boxed = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) boxed[i] = nums[i];
Arrays.sort(boxed, Comparator.reverseOrder());

// Option 2: sort ascending, then reverse in-place
Arrays.sort(nums);
for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
    int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
}

// Option 3: sorted stream (if you only need the result, not a modified original)
int[] sorted = IntStream.of(nums).boxed()
    .sorted(Comparator.reverseOrder())
    .mapToInt(Integer::intValue).toArray();

Option 1 is clearest in an interview. Option 2 avoids boxing entirely if you genuinely need descending without allocating.

Sort decision flow showing which Arrays.sort overload to use and the subtraction trap

Three Ways to Write a Java Comparator

Lambda

The everyday choice. (a, b) -> expr returns negative if a should come first, positive if b should, zero if equal.

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

Factory Methods

Java 8 added Comparator.comparing(), which takes a key extractor and returns a full comparator. This is the cleanest way to write multi-field sorts, and it avoids boxing for primitive fields.

list.sort(Comparator.comparing(Person::getLastName)
                    .thenComparing(Person::getFirstName));

Comparator.comparingInt(String::length)    // avoids Integer boxing
Comparator.comparingLong(Item::getId)
Comparator.comparingDouble(Product::getPrice)

Direct Implementation

Rarely needed in interviews, but useful for a named, reusable comparator you want to store as a class field.

static final Comparator<int[]> BY_START = (a, b) -> Integer.compare(a[0], b[0]);

The Subtraction Trap Will Cost You

This is the most common quiet bug in Java interview code, and quiet is the whole problem. Never write (a, b) -> a - b to compare integers. It overflows and it doesn't tell you.

When a = Integer.MAX_VALUE (2,147,483,647) and b = -1, the subtraction produces 2,147,483,648. That number doesn't fit in an int, so it wraps to Integer.MIN_VALUE. Negative. Wrong sign. Your comparator now says the largest element should come first when it shouldn't. The sort runs to completion and hands you a confidently wrong answer.

// WRONG, silently corrupt for large values
list.sort((a, b) -> a - b);

// CORRECT, two branches, no arithmetic
list.sort((a, b) -> Integer.compare(a, b));

// ALSO CORRECT, factory method, avoids boxing too
list.sort(Comparator.comparingInt(x -> x));

Integer.compare(a, b) uses relational operators internally (a < b ? -1 : a == b ? 0 : 1), costs nothing extra, and cannot overflow. There is no reason to write the subtraction version.

Chain Comparators for Multi-Key Sorts

Chaining with `thenComparing`

// Sort by department ascending, then by age ascending within each department
list.sort(Comparator.comparing(Employee::getDept)
                    .thenComparingInt(Employee::getAge));

Reversing Part of a Chain

reversed() flips the entire preceding comparator, not just the last key. If you chain first and call reversed() at the end, you reverse both keys. That's almost never what you wanted.

// Reverses BOTH keys, probably wrong
Comparator.comparing(Employee::getDept)
          .thenComparingInt(Employee::getAge)
          .reversed();

// Reverses only age, keeps dept ascending
Comparator.comparing(Employee::getDept)
          .thenComparing(e -> e.getAge(), Comparator.reverseOrder());

To flip only one key, pass Comparator.reverseOrder() as the second argument to that specific comparing() call:

// Name ascending, age descending
list.sort(Comparator.comparing(Person::getName)
                    .thenComparing(Person::getAge, Comparator.reverseOrder()));

The `reversed()` Type-Inference Problem

Comparator.comparing(Person::getName).reversed() sometimes fails to compile because the Java compiler loses track of the generic type through the reversal. It's one of those moments where you stare at a red squiggle and wonder why the most basic thing doesn't work.

// Fails sometimes, compiler can't infer T after reversed()
Comparator.comparing(Person::getName).reversed();

// Always works, explicit type witness
Comparator.<Person, String>comparing(Person::getName).reversed();

// Cleanest fix, pass reverseOrder() directly
Comparator.comparing(Person::getName, Comparator.reverseOrder());

Natural Order, Reverse Order, and Nulls

Comparator.naturalOrder()    // same as (a, b) -> a.compareTo(b)
Comparator.reverseOrder()    // same as (a, b) -> b.compareTo(a)

// Null-safe: push nulls to one end
list.sort(Comparator.nullsFirst(Comparator.comparing(Person::getName)));

Patterns Worth Having Ready

Sort 2D array by first column (intervals, meetings, etc.)

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

Sort 2D array by first column, break ties by second

Arrays.sort(intervals, (a, b) ->
    a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));

// Or with factory methods
Arrays.sort(intervals, Comparator.comparingInt((int[] a) -> a[0])
                                 .thenComparingInt(a -> a[1]));

Sort strings by length, then lexicographically

Arrays.sort(words, Comparator.comparingInt(String::length)
                             .thenComparing(Comparator.naturalOrder()));

Sort a frequency map's entries by value descending, then key ascending

// Type inference on Map.Entry generics gets fiddly, lambdas are clearer here
entries.sort((a, b) -> {
    int cmp = Integer.compare(b.getValue(), a.getValue());  // descending
    return cmp != 0 ? cmp : a.getKey().compareTo(b.getKey());
});

Stability: When It Actually Bites You

Stable sort preserves the relative order of equal elements. Arrays.sort(T[]) and Collections.sort are both stable. Arrays.sort(int[]) is not, but for primitives it doesn't matter because equal values are physically identical.

Where this trips candidates up: sorting the same data twice to achieve a two-key sort. Do the passes in the wrong order and the final result is wrong. Sort by the secondary key first, then by the primary key with a stable sort, and you get the right combined order automatically.

// Two-pass stable trick: secondary key first, primary key second
Arrays.sort(people, Comparator.comparing(Person::getFirstName));   // secondary
Arrays.sort(people, Comparator.comparing(Person::getLastName));    // primary (stable)
// Result: sorted by lastName, ties broken by firstName

The thenComparing chain is cleaner in practice. But knowing the two-pass approach shows you understand why stability exists, which is a better signal than just knowing the API.

The Clone Trap

Arrays.sort mutates in place. If you need the original order preserved after sorting, clone first or sort an index array instead.

int[] sorted = nums.clone();
Arrays.sort(sorted);

// Or sort indices when you need to map back to original positions
Integer[] indices = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) indices[i] = i;
Arrays.sort(indices, (i, j) -> Integer.compare(nums[i], nums[j]));
// indices[k] now gives the k-th smallest element's original position

Quick Reference

// Ascending, primitives
Arrays.sort(int[] arr)

// Ascending, objects (natural order)
Arrays.sort(T[] arr)
Collections.sort(List<T> list)

// Custom comparator, objects only
Arrays.sort(T[] arr, Comparator<T> comp)
list.sort(Comparator<T> comp)

// Safe integer comparison, never subtract
Integer.compare(a, b)
Comparator.comparingInt(fn)

// Multi-key sort
Comparator.comparing(fn1).thenComparing(fn2)

// Descending (pick one)
Comparator.comparingInt(fn).reversed()
Comparator.comparing(fn, Comparator.reverseOrder())

// Reverse a primitive int array after sorting
for (int i = 0, j = arr.length - 1; i < j; i++, j--) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }

Comparator bugs are silent bugs, which makes them the most interview-unfriendly kind. The code runs, the interviewer nods, and then the hidden test case reveals your sort was backwards the entire time. If you want to practice narrating comparator decisions out loud so you catch these before they land, SpaceComplexity runs voice mock interviews with rubric-based feedback on exactly that kind of communication.

Key Takeaways

Arrays.sort(int[]) is unstable and accepts no comparator. Arrays.sort(T[]) is stable and accepts a comparator.
(a, b) -> a - b overflows at Integer.MAX_VALUE. Use Integer.compare(a, b). Every time.
reversed() flips the whole preceding chain. To reverse one key, pass Comparator.reverseOrder() as the second argument to that comparing() call.
Comparator.comparingInt(fn) avoids boxing. Prefer it over comparing() when extracting int fields.
Arrays.sort mutates in place. Clone if you need the original order.
Stable sort enables multi-key sorting via two sequential single-key passes. Secondary key first, primary key second.

For more on how Java's collections work under pressure, see Java for Coding Interviews and Stable Sort: The Property That Makes Multi-Key Sorting Actually Work. For a direct comparison with Python's approach, Python Sort for Coding Interviews covers key=, cmp_to_key, and the equivalent traps.