Arrays.sort in Java

Arrays.sort: primitive types use Dual-Pivot Quicksort; objects use TimSort (merge-based, stable). ParallelSort exists for large arrays.

Know the stability and memory properties, not every intrinsic.

Where used

Primitives: Dual-Pivot Quicksort. Objects: TimSort (stable, run-aware). Production rule: do not sort yourself, unless under special constraints.

Depth

Arrays.sort is overloaded and chooses different methods depending on the element type. In object arrays, the relative order of equally rated elements is maintained. Arrays of primitive types are processed with a different, representation-specific strategy.

For objects, either their natural order or a Comparator determines the outcome. The Comparator must be consistent, particularly observing transitivity and sign changes. A faulty Comparator can cause not only an unexpected order but also runtime errors.

Difficulty levels

1. Distinguish between primitive and object arrays regarding sorting semantics.
2. Design a transitive Comparator for multiple fields.
3. Leverage stability for a multi-level object sorting.

Pitfalls

Subtraction as an int Comparator can overflow. Integer.compare and chained Comparators are safer. Additionally, stability should not be generalized from one overload to all others.