Sorting arrays

Arrays.sort(numbers);              // ascending
Arrays.sort(a, fromIndex, toIndex);
Collections.sort(list);
list.sort(null);                   // natural order

Sorting objects requires knowing what “in order” means. Either the class implements Comparable, or you supply a Comparator.

Comparators

people.sort(Comparator.comparing(Person::lastName));

people.sort(Comparator.comparing(Person::lastName)
                      .thenComparing(Person::firstName)
                      .reversed());

numbers.sort(Comparator.naturalOrder());

Prefer Comparator.comparing over a hand-written comparison. Writing (a, b) -> a.age() - b.age() looks fine and overflows for large or negative values, producing the wrong sign. Comparator.comparingInt(Person::age) cannot.

A comparator must be consistent: if it says a < b and b < c, it must say a < c. An inconsistent one throws IllegalArgumentException: Comparison method violates its general contract: an error message that confuses everyone the first time, and which almost always means a comparator returning inconsistent results, often because it compares floating-point values containing NaN.

Two algorithms

Arrays.sort behaves differently depending on what it is sorting.

Primitives get a dual-pivot quicksort. It is not stable, but stability is meaningless for primitives, two equal ints are indistinguishable, and it avoids allocating a second array.

Objects get TimSort, which is stable and exploits runs of already-ordered data. Stability matters here: sort by first name, then by last name, and people with the same surname stay in first-name order. Without stability that second sort would scramble the first.

TimSort is also close to linear on partly sorted input, which real data very often is.

Sorting a primitive array descending

There is no built-in way. Arrays.sort has no comparator overload for primitives, because a comparator would force boxing. Options: sort ascending and reverse in place, or box to Integer[] and use Comparator.reverseOrder().

Cost

O(n log n) comparisons for both. Do not sort inside a loop. Sorting once outside it is the usual fix for a surprisingly slow method.

Sorting part of an array

Arrays.sort(a, 0, 10);      // first ten elements only

The range is half-open: from inclusive, to exclusive, matching every other range API in the library.

Parallel sorting

Arrays.parallelSort(values);

Splits the work across the common ForkJoin pool. It wins on large arrays, the threshold is in the tens of thousands, and loses on small ones, because coordinating threads costs more than the sort. Measure before switching; the default is right far more often than not.

Sorting a stream

List<Person> sorted = people.stream()
        .sorted(Comparator.comparing(Person::lastName))
        .toList();

This leaves the original untouched and produces a new list, which is what you want when the source should not change. It allocates, so for sorting a large list you already own, list.sort(...) in place is cheaper.