Arrays.sort in Java

Arrays.sort: primitive Typen nutzen Dual-Pivot Quicksort; Objekte TimSort (Merge-basiert, stabil). ParallelSort existiert für grosse Arrays.

Kenn die Stabilitäts- und Speichereigenschaften, nicht jeden Intrinsic.

Wo gebraucht

Primitives: Dual-Pivot Quicksort. Objekte: TimSort (stable, Run-aware). Produktionsregel: nicht selbst sortieren, ausser Spezialconstraints.

Vertiefung

Arrays.sort ist überladen und wählt abhängig vom Elementtyp unterschiedliche Verfahren. Bei Objektarrays bleibt die gegenseitige Abfolge gleich bewerteter Elemente erhalten. Arrays primitiver Typen werden mit einer anderen, auf diese Darstellung zugeschnittenen Strategie verarbeitet.

Für Objekte bestimmt entweder ihre natürliche Ordnung oder ein Comparator das Ergebnis. Der Comparator muss konsistent sein, insbesondere Transitivität und Vorzeichenwechsel beachten. Ein fehlerhafter Comparator kann nicht nur eine unerwartete Ordnung, sondern auch Laufzeitfehler verursachen.

Schwierigkeitsstufen

1. Primitive und Objektarrays hinsichtlich der Sortiersemantik unterscheiden.
2. Einen transitiven Comparator für mehrere Felder entwerfen.
3. Stabilität für eine mehrstufige Objektsortierung ausnutzen.

Fallstricke

Subtraktion als int-Comparator kann überlaufen. Sicherer sind Integer.compare und verkettete Comparatoren. Ausserdem darf Stabilität nicht pauschal von einer Überladung auf alle anderen übertragen werden.