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.

saying these in an interview costs you the question

  • 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

resolving links…