Sorting and Comparators

1.Sorting arrays and lists

Arrays.sort(int[]) sorts primitives in ascending order in O(n log n). Collections.sort(list) or list.sort(null) sorts a list. To sort primitives in descending order, sort ascending and read backwards, or use a boxed Integer[] with a reversed comparator.

2.Comparators: sorting by your own rule

A comparator takes two elements and returns a negative number if the first should come first, zero if they're equal and positive otherwise. Lambdas keep it short. Comparator.comparingInt and thenComparing build rules step by step.

Sorting intervals by start time (int[][]) is one of the most common uses.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] intervals = {{5, 7}, {1, 3}, {2, 4}};
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        System.out.println(Arrays.deepToString(intervals));

        List<String> words = new ArrayList<>(List.of("pear", "fig", "banana", "kiwi"));
        words.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
        System.out.println(words);

        Integer[] boxed = {3, 1, 2};
        Arrays.sort(boxed, Collections.reverseOrder());
        System.out.println(Arrays.toString(boxed));
    }
}

[[1, 3], [2, 4], [5, 7]]
[fig, kiwi, pear, banana]
[3, 2, 1]

3.The subtraction trap

You'll often see (a, b) -> a - b as a comparator. It works for small numbers but overflows when values are large or of opposite signs: Integer.MIN_VALUE - 1 wraps to a huge positive number, so the order comes out wrong. Use Integer.compare(a, b) instead; it never overflows.