skip to content

How does Arrays.sort behave for primitives vs objects (algorithm, stability, custom order), and what does Arrays.stream / parallelSort add?

level: seniorimportance: should knowfreq 48%

answer

  1. Objects: TimSort, stable, comparator + natural order
  2. Primitives: dual-pivot quicksort, unstable, no comparator, O(n^2) worst case
  3. In place, ascending, returns void
  4. parallelSort = fork/join for big arrays
  5. Arrays.stream -> IntStream/.../Stream<T> for map/filter/reduce

basics

~20 s

Arrays.sort orders an array ascending in place. For objects it's a stable merge-style sort and you can pass a Comparator for custom order; for primitives it's an unstable quicksort and there's no comparator. Arrays.stream turns an array into a stream for map/filter/reduce; parallelSort sorts using multiple threads.

solid answer

~40 s

Arrays.sort(a) sorts in place, ascending. For object arrays it uses TimSort, a stable, adaptive merge sort (O(n log n)); stable means equal elements keep their original order, which matters when sorting by multiple keys. You can pass a Comparator to define custom ordering, and there are range overloads. For primitive arrays it uses a dual-pivot quicksort: average O(n log n) but worst case O(n^2) on adversarial input, and it is unstable and takes no comparator (stability is meaningless for indistinguishable primitives). Arrays.parallelSort splits the work across the fork/join pool for large arrays, also stable for objects. Arrays.stream(a) creates a stream (IntStream/LongStream/DoubleStream for those primitives, or Stream<T> for objects) so you can map/filter/sum/collect functionally; overloads let you stream a sub-range. These are the modern way to process arrays without manual loops.

code

java · 19 lines
java
// Primitives: ascending only, no comparator
int[] nums = {3, 1, 2};
Arrays.sort(nums);                 // {1, 2, 3} (dual-pivot quicksort, unstable)

// Objects: natural order or a Comparator; stable (TimSort)
String[] names = {"bob", "amy", "cara"};
Arrays.sort(names);                              // natural order
Arrays.sort(names, Comparator.reverseOrder());  // custom order

// To sort primitives descending, box first:
Integer[] boxed = {3, 1, 2};
Arrays.sort(boxed, Comparator.reverseOrder());   // {3, 2, 1}

// Stream processing
int sum = Arrays.stream(nums).filter(n -> n > 1).sum();   // 5
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());

// Large array, multi-core
Arrays.parallelSort(new int[1_000_000]);

go deeper

for a junior

Can sort an int[] or String[] ascending with Arrays.sort and knows it sorts in place.

for a middle

Knows objects accept a Comparator while primitives don't, and uses Arrays.stream for basic map/filter/sum.

for a senior

Explains TimSort vs dual-pivot quicksort, stability semantics, the O(n^2) primitive worst case, boxing to customize primitive order, and chooses sort vs parallelSort vs stream appropriately.

for a principal

Reasons about algorithmic guarantees for untrusted input (quicksort worst case), parallelism tradeoffs and the shared ForkJoinPool, and sets guidance on comparator design and functional array processing across the codebase.

## Arrays.sort — what it does `Arrays.sort(a)` rearranges the array's elements into **ascending order, in place** (it returns void; it mutates `a`). It is the standard way to sort an array. ## Two different algorithms: objects vs primitives The behavior — and the guarantees — differ by element type, which is the heart of this topic. **Object arrays (`Object[]`, `T[]`):** sorted with **TimSort**, a hybrid of merge sort and insertion sort that is: - **Stable** — equal elements keep their original relative order. This is essential when you sort by one key after another (sort by name, then stably by age, to get age-then-name ordering). - **Adaptive** — it runs faster (near O(n)) on data that's already partly sorted. - **O(n log n)** worst case; needs O(n) extra space. Ordering comes from the elements' **natural order** (`Comparable.compareTo`) or a **`Comparator`** you pass: `Arrays.sort(a, comparator)`. There are range overloads `sort(a, from, to[, cmp])`. **Primitive arrays (`int[]`, `double[]`, ...):** sorted with a **dual-pivot quicksort**: - **Unstable** — but stability is **meaningless** for primitives, since two equal `int`s are indistinguishable; swapping them changes nothing observable. - **No `Comparator`** overload — you can only sort ascending. To sort primitives descending or by a custom rule you must box to `Integer[]` (then `Comparator.reverseOrder()`), or sort then reverse. - Average **O(n log n)**, but **worst case O(n^2)** on carefully constructed adversarial inputs (a known consideration for untrusted data). Why two algorithms? Quicksort is fast and cache-friendly with no extra allocation for value types; stability would be wasted on them. Objects need stability and a comparator, which merge sort provides naturally. ## Arrays.parallelSort `Arrays.parallelSort(a)` sorts large arrays by **splitting the work across multiple threads** (the common ForkJoinPool), merging the sorted pieces. It is **stable for object arrays** and uses the same ordering rules/comparator overloads. For small arrays it falls back to the sequential sort (parallelism overhead isn't worth it). Use it for big arrays on multi-core machines; for typical sizes plain `sort` is fine. ## Arrays.stream — functional processing `Arrays.stream(a)` produces a **stream** so you can process the array with `map`/`filter`/`reduce`/`collect` instead of loops: - `Arrays.stream(int[])` -> **`IntStream`** (similarly `LongStream`, `DoubleStream`) — specialized primitive streams with `sum()`, `average()`, `boxed()`, etc. - `Arrays.stream(T[])` -> **`Stream<T>`**. - Range overloads `Arrays.stream(a, from, to)` stream only a slice. This is the idiomatic bridge from arrays to the Streams API and to collections (`.boxed().collect(toList())`). ## Putting it together - Sort ascending, any type -> `Arrays.sort`. - Custom/descending order or multi-key stable sort -> object array + `Comparator` (box primitives if needed). - Huge array, multi-core -> `Arrays.parallelSort`. - Transform/aggregate functionally, or convert to a collection -> `Arrays.stream`. ## Common pitfalls 1. Expecting a `Comparator` overload for `int[]` (there isn't one). 2. Relying on **stability for primitives** (irrelevant) or **forgetting stability** when it matters for objects. 3. Ignoring the **O(n^2) quicksort worst case** for untrusted primitive input. 4. Using `parallelSort` on tiny arrays (no benefit, just overhead). ## Mental model `sort` quietly picks the right algorithm for the element type: a stable, comparator-aware merge sort for objects; a lean, unstable, comparator-less quicksort for primitives. `parallelSort` is the multi-threaded variant; `stream` is the on-ramp to functional pipelines.

  • Why is there no Comparator version of Arrays.sort(int[])?
    Primitives have a single fixed natural order and are indistinguishable when equal, so a custom comparator (and stability) adds nothing. To customize, box to Integer[] and use the object overload.
  • When does stability actually matter?
    When sorting objects by successive keys: a stable sort preserves the previous ordering among equal elements, so sorting by secondary key then primary key yields the combined ordering. Unstable sorts can scramble the prior order.

  • Expecting a Comparator overload for primitive arrays
  • Claiming primitive sort is stable as a meaningful property
  • Forgetting object sort stability when sorting by multiple keys
  • Assuming sort returns a new sorted array (it mutates in place, returns void)
  • Using parallelSort for small arrays expecting a speedup

context