Which sort does Arrays.sort use, and why does it depend on the type?

The Answer

Say this in the room. 45 seconds.

• Arrays.sort(int[]) runs dual-pivot quicksort. Arrays.sort(Object[]) runs TimSort. List.sort and Collections.sort are the object path.
• The reason is stability, not speed. Two Employee objects can compare equal on department and still be different people, so their order carries information and must be preserved. Two equal ints are the same value — you cannot write a test that tells which one came first.
• Because primitives need no stability, their sort is allowed to be in place, with no allocation. TimSort needs a working array, so the object sort costs O(n) extra memory.
• TimSort is adaptive: it finds runs that are already ordered and merges them. On sorted input it does exactly n−1 comparisons, not n log n.
• Since JDK 14 the primitive sort is adaptive too, and has a depth guard that falls back to heap sort — so "quicksort can be forced to O(n²)" is no longer true of Arrays.sort.
• The practical trap is the comparator. (a, b) -> a - b overflows and mis-sorts silently. A non-transitive comparator may throw IllegalArgumentException — and may not.

Understand It

Stability is the whole reason for the split

Sort by one key, then by a second. A stable sort preserves the first ordering inside each group of the second — which is how every "group by department, alphabetical within group" requirement is actually implemented.

// Sort by name first, then by department. If the department sort is stable,
// the names stay in order inside each department.
Emp[] a = staff().toArray(new Emp[0]);
Arrays.sort(a, Comparator.comparing(Emp::name));
Arrays.sort(a, Comparator.comparing(Emp::dept));
System.out.println("  Arrays.sort (TimSort) : " + show(a));

Emp[] b = staff().toArray(new Emp[0]);
Arrays.sort(b, Comparator.comparing(Emp::name));
unstableSort(b, 0, b.length - 1, Comparator.comparing(Emp::dept));
System.out.println("  quicksort  (unstable) : " + show(b));

  Arrays.sort (TimSort) : Eng/Ana Eng/Cara Eng/Eli Ops/Fay Sales/Bo Sales/Dev
  quicksort  (unstable) : Eng/Eli Eng/Ana Eng/Cara Ops/Fay Sales/Dev Sales/Bo

Both results are correctly sorted by department. Only one kept the names in order, and the unstable one did not corrupt anything — it just discarded work the previous sort had done.

Now ask the same question of int[]. Sort {3, 1, 3} and you get {1, 3, 3}. Which 3 is first? The question has no meaning: an int has no identity, so no program can distinguish the two outcomes. Stability is unobservable for primitives, so the JDK does not pay for it — and the payment is real, because a stable merge sort needs somewhere to merge into.

There is a second, blunter reason the two paths differ, visible in the signatures:

public static void sort(int[] a)                            // no comparator parameter exists
public static <T> void sort(T[] a, Comparator<? super T> c) // ordering is supplied by you

int has exactly one natural order and no way to supply another. Everything interesting about object sorting — stability, comparator contracts, the exception below — follows from that second signature.

TimSort is adaptive, and you can prove it from outside

Arrays.sort does not report which algorithm it chose. But a comparator is a function you supply, so you can count how many times it is called — and the count identifies the algorithm.

int n = 1_000_000;
Comparator<Integer> natural = Integer::compare;

// A merge sort that detects existing runs needs one pass — n-1 comparisons —
// to confirm the whole array is already one run. A quicksort cannot: it has to
// partition regardless, and never learns the input was sorted.
for (String shape : List.of("already sorted", "reverse sorted", "sorted, 1k shuffled", "random")) {
    Random r = new Random(42);
    Integer[] a = switch (shape) {
        case "already sorted"      -> boxed(n, i -> i);
        case "reverse sorted"      -> boxed(n, i -> n - i);
        case "sorted, 1k shuffled" -> boxed(n, i -> i < n - 1000 ? i : r.nextInt());
        default                    -> boxed(n, i -> r.nextInt());
    };
    int[] calls = {0};
    Arrays.sort(a, counting(natural, calls));
    System.out.println("  " + shape + " -> " + calls[0] + " comparisons");
}
System.out.println("  n log2 n would be    -> " + (long) (n * (Math.log(n) / Math.log(2))));

// List.sort and Collections.sort delegate to the same code, so they inherit it.
List<Integer> list = new ArrayList<>(Arrays.asList(boxed(n, i -> i)));
int[] viaList = {0};
list.sort(counting(natural, viaList));
System.out.println("  List.sort on sorted  -> " + viaList[0] + " comparisons");

  already sorted -> 999999 comparisons
  reverse sorted -> 999999 comparisons
  sorted, 1k shuffled -> 1007773 comparisons
  random -> 18640524 comparisons
  n log2 n would be    -> 19931568
  List.sort on sorted  -> 999999 comparisons

Read the first two lines carefully. 999,999 is exactly n−1 — one comparison per adjacent pair, the minimum needed to check that a million elements are ordered. TimSort walks the array once, finds it is a single ascending run, and stops. Reverse-sorted input costs the same, because a descending run is detected and reversed in place.

That reversal has a condition worth knowing: the run must be strictly descending. Equal neighbours end it, because reversing a block containing equal elements would swap their order and break stability. Descending data with duplicates therefore fragments into many short runs — the same million elements cost around 436,000 comparisons instead of 999,999 when every value appears twice. Stability is not a feature bolted on top of TimSort; it constrains what the algorithm is allowed to notice.

The third line is the one that matters at work. A million rows arriving mostly sorted, with a thousand out of place, costs 1,007,773 comparisons rather than the 19.9 million the textbook bound predicts. This is not an optimisation you enable; it is why appending to a sorted list and re-sorting is much cheaper than people expect.

The random case, 18.6 million, sits just under n log₂ n — which is the guarantee. TimSort never degrades; the worst case is the bound.

The comparator is where the bugs are, and the loud one is not the dangerous one

(a, b) -> a - b reads as obviously correct and is not. Subtraction overflows.

// The comparator every codebase has written at least once.
Comparator<Integer> subtract = (x, y) -> x - y;

Integer[] small = { 7, 2, 9, 4 };
Arrays.sort(small, subtract);
System.out.println("  small values      : " + Arrays.toString(small) + "   looks fine");

// Same comparator, values far apart. x - y overflows and flips sign.
Integer[] wide = { Integer.MIN_VALUE + 1, 5, Integer.MAX_VALUE, -3 };
Arrays.sort(wide, subtract);
System.out.println("  wide values       : " + Arrays.toString(wide));

Integer[] fixed = { Integer.MIN_VALUE + 1, 5, Integer.MAX_VALUE, -3 };
Arrays.sort(fixed, Integer::compare);
System.out.println("  Integer::compare  : " + Arrays.toString(fixed));

// And at scale it stays quiet — no exception, just an array that is not sorted.
Random r = new Random(3);
Integer[] big = boxed(1000, i -> r.nextInt());
Arrays.sort(big, subtract);
System.out.println("  1000 full-range   : threw? no, sorted? " + isSorted(big));

  small values      : [2, 4, 7, 9]   looks fine
  wide values       : [5, 2147483647, -2147483647, -3]
  Integer::compare  : [-2147483647, -3, 5, 2147483647]
  1000 full-range   : threw? no, sorted? false

Integer.MAX_VALUE - (-3) is not a large positive number; it wraps to a negative one, so the comparator reports that the largest value is smaller than a small one. Nothing throws. The array comes back visibly unsorted and the program carries on.

That is the shape of this bug in production: it passes every test written with small ids, and it fails the day the id sequence, a timestamp difference, or a currency amount in minor units crosses the overflow boundary. Integer.compare, Long.compare and Comparator.comparingInt exist precisely so subtraction is never needed.

The other kind of broken comparator is one that is not a total order. This is the one people have heard of, because it sometimes throws:

// "Close enough counts as equal" — a real requirement, and not a total order.
// a==b and b==c does not give a==c once the gaps add up.
Comparator<Integer> fuzzy = (x, y) -> Math.abs(x - y) <= 10 ? 0 : Integer.compare(x, y);

System.out.println("  transitive? 5==12 " + (fuzzy.compare(5, 12) == 0)
                 + ", 12==20 " + (fuzzy.compare(12, 20) == 0)
                 + ", so 5==20? " + (fuzzy.compare(5, 20) == 0));

for (int size : new int[] { 20, 31, 32, 200 }) {
    Random r = new Random(1);
    Integer[] a = boxed(size, i -> r.nextInt(100));
    try {
        Arrays.sort(a, fuzzy);
        System.out.println("  n=" + size + " -> sorted without complaint");
    } catch (IllegalArgumentException e) {
        System.out.println("  n=" + size + " -> " + e.getMessage());
    }
}

  transitive? 5==12 true, 12==20 true, so 5==20? false
  n=20 -> sorted without complaint
  n=31 -> sorted without complaint
  n=32 -> sorted without complaint
  n=200 -> Comparison method violates its general contract!

Look at what the array size did. The same broken comparator, on the same kind of data, sorted quietly at 20, 31 and 32 elements and threw at 200.

Below 32 elements TimSort never merges at all — it runs a binary insertion sort over the whole array, and the contract check lives in the merge. Above that, detection depends on whether the merge happens to run off the end of a run, which depends on the data. The exception is a diagnostic that fires sometimes, not a validation. Its absence proves nothing, which is why this bug reaches production in a small test fixture and surfaces as a support ticket at scale.

When this throws in a live system, the comparator is the bug, and the two usual causes are subtraction overflow and a compare that returns 0 for "similar" rather than "equal". Suppressing it with -Djava.util.Arrays.useLegacyMergeSort=true restores the pre-Java-7 sort, which silently produces a wrongly ordered array instead. That flag buys a green build and keeps the defect.

What the type costs, measured

int n = 1_000_000;
Random r = new Random(9);
int[] rand = new int[n], asc = new int[n];
Integer[] box = new Integer[n];
for (int i = 0; i < n; i++) { int v = r.nextInt(); rand[i] = v; box[i] = v; asc[i] = i; }

for (int w = 0; w < 2; w++) { Arrays.sort(rand.clone()); Arrays.sort(asc.clone()); }

long t = System.nanoTime();
Arrays.sort(asc.clone());
System.out.println("  int[] already sorted : " + (System.nanoTime() - t) / 1_000_000 + " ms");

t = System.nanoTime();
Arrays.sort(rand.clone());
System.out.println("  int[] random         : " + (System.nanoTime() - t) / 1_000_000 + " ms");

t = System.nanoTime();
Arrays.sort(box.clone(), Integer::compare);
System.out.println("  Integer[] random     : " + (System.nanoTime() - t) / 1_000_000 + " ms");

// Footprint is arithmetic, not measurement: 4 bytes per int, against a 4-byte
// compressed reference plus a 16-byte Integer object for every element.
System.out.println("  int[] holds          : " + (4L * n >> 20) + " MB");
System.out.println("  Integer[] holds      : " + (20L * n >> 20) + " MB, plus a merge buffer while sorting");

  int[] already sorted : 26 ms
  int[] random         : 385 ms
  Integer[] random     : 3380 ms
  int[] holds          : 3 MB
  Integer[] holds      : 19 MB, plus a merge buffer while sorting

Two things in this output are worth more than the headline ratio.

The first line refutes the textbook answer. An already-sorted int[] costs a small fraction of a random one, which a pure quicksort could not manage — quicksort has no way to notice its input is sorted. Since JDK 14 DualPivotQuicksort scans for existing runs first and merges them when it finds enough, so the primitive path is adaptive too. The same rewrite added a recursion-depth limit that falls back to heap sort, which is why "an attacker can feed you input that makes Arrays.sort quadratic" is a stale answer for modern JDKs, whatever it is still worth on a whiteboard.

The second is the memory column. int[] is 4 bytes per element. Integer[] is a reference plus a separate heap object per element — roughly five times the footprint, spread across the heap so every comparison is a pointer dereference and a likely cache miss. TimSort then allocates a working array on top. When a sort of a few million elements is a real cost in a service, the fix is almost always to stop boxing, not to change algorithm.

Treat the millisecond numbers as an order of magnitude only. They came from one loaded developer machine with no JMH harness, and the object/primitive ratio moved between 5x and 11x across runs here depending on when GC ran.

Reference

The correct implementation, the configuration, and the migration path. Copy from here.

Choosing the call

parallelSort is not a free upgrade: it falls back to the sequential sort below about 8,192 elements, and it uses the common ForkJoinPool, so it competes with every other parallel stream in the JVM.

Comparators that are correct

// Never subtract. These are overflow-safe and read better.
Comparator.comparingInt(Employee::salary)
Comparator.comparingLong(Order::timestamp)
Comparator.comparingDouble(Item::weight)

// Multi-key: department ascending, then salary descending, then name as a tiebreak.
Comparator<Employee> order =
    Comparator.comparing(Employee::dept)
              .thenComparing(Employee::salary, Comparator.reverseOrder())
              .thenComparing(Employee::name);

// Nulls, without a null check in every comparator.
Comparator.nullsFirst(Comparator.comparing(Employee::manager))

// Locale-aware. String.CASE_INSENSITIVE_ORDER is ASCII-minded; java.text.Collator
// is what you want for user-visible names in a non-English locale.
Comparator.comparing(Person::name, Collator.getInstance(Locale.forLanguageTag("de")))

// Reverse a whole multi-key comparator — note this reverses ALL keys.
order.reversed()

Two rules cover nearly every comparator bug:

1. Never write a - b. Use Integer.compare, Long.compare, or a comparingInt-family factory.
2. Return 0 only for elements that are genuinely interchangeable. "Within a tolerance" is not equality, and a sort is not the right tool for it — cluster first, then sort the clusters.

Making a class sortable

// Comparable = the one natural order, baked in. Use it when there is exactly
// one obvious ordering and it agrees with equals.
record Money(long minorUnits, String currency) implements Comparable<Money> {
    @Override public int compareTo(Money other) {
        if (!currency.equals(other.currency))
            throw new IllegalArgumentException("cannot order " + currency + " against " + other.currency);
        return Long.compare(minorUnits, other.minorUnits);   // not subtraction: longs overflow too
    }
}

compareTo should be consistent with equals — a.compareTo(b) == 0 exactly when a.equals(b). It is not enforced, and when it is violated, TreeSet and TreeMap misbehave in ways a HashSet would not: they use compareTo, not equals, so an element that compares 0 is treated as a duplicate and silently dropped.

Everything else wants a Comparator, passed in at the call site.

Sorting a stream, and when not to

// Fine: bounded input, you need the whole thing ordered.
List<Employee> byPay = staff.stream()
    .sorted(Comparator.comparingInt(Employee::salary).reversed())
    .toList();

// Wrong shape: sorted() buffers the entire stream before emitting anything,
// so this reads every row to print ten.
staff.stream().sorted(cmp).limit(10).forEach(this::print);

// Right shape for top-k: a bounded heap, O(n log k) time and O(k) memory.
PriorityQueue<Employee> top = new PriorityQueue<>(Comparator.comparingInt(Employee::salary));
for (Employee e : staff) {
    top.offer(e);
    if (top.size() > 10) top.poll();          // evict the smallest
}

For a database-backed list, the correct answer to both is ORDER BY ... LIMIT 10 with a matching index — sorting in the JVM means the rows crossed the network first.

Diagnosing "Comparison method violates its general contract!"

// Drop this into a test to find the offending triple. It is O(n^3), so run it
// over the smallest input that reproduces, not over production data.
static <T> void assertTotalOrder(List<T> items, Comparator<T> c) {
    for (T a : items) for (T b : items) {
        if (Integer.signum(c.compare(a, b)) != -Integer.signum(c.compare(b, a)))
            throw new AssertionError("not antisymmetric: " + a + " / " + b);
        for (T d : items) {
            if (c.compare(a, b) <= 0 && c.compare(b, d) <= 0 && c.compare(a, d) > 0)
                throw new AssertionError("not transitive: " + a + " / " + b + " / " + d);
        }
    }
}

Check, in this order: subtraction anywhere in the comparator; a compare returning 0 for "similar"; a comparator reading a mutable field that changed mid-sort; and a Comparable whose compareTo disagrees with equals.

Scenarios

Real situations, with the decision and the argument.

1. A report has started showing rows in the wrong order, and only for the largest customer.

Sort by an id or an epoch-millisecond difference, and the comparator is almost certainly subtracting. It works until two values are far enough apart for the subtraction to overflow — which is why the biggest account, the oldest record or the highest sequence number is the one that breaks.

Nothing threw, so there is no stack trace to search for. Grep the codebase for - inside a compare or compareTo before you reach for a debugger; on most teams that search finds the bug in a minute. The fix is Integer.compare / Long.compare, and the regression test needs values near the range boundary rather than the 1, 2, 3 the original test used.

2. Production throws Comparison method violates its general contract! and someone has found the flag that makes it stop.

-Djava.util.Arrays.useLegacyMergeSort=true will indeed make it stop. It reverts to the pre-Java-7 merge sort, which tolerates an inconsistent comparator by producing a wrongly ordered result instead of complaining. The exception was the only reason anyone knew the ordering was wrong.

Push back on the flag and fix the comparator. It is worth saying out loud that the exception is a gift — it is the JDK telling you, before a customer does, that your ordering has been unreliable for as long as the comparator has existed. If a same-day mitigation is genuinely needed, the flag is a deliberate, ticketed, time-boxed decision, not a config change.

3. Grouped results lost their alphabetical order after someone "optimised" the sort.

Someone replaced a two-pass stable sort with a single hand-rolled comparator, or with a sort that is not stable. The two-pass version — sort by name, then by department — is correct precisely because TimSort is stable, and it is often the clearer code.

Both approaches are defensible. The one-pass thenComparing chain is explicit about the full ordering and does not depend on a stability guarantee the next reader has to know about; the two-pass version composes better when the second key is chosen at runtime. What is not defensible is the two-pass version on a sort that is not stable, which is exactly what happens when the data moves to a parallelStream or a primitive array.

4. A service sorting a few million rows per request is at its heap limit.

Look at the element type before the algorithm. List<Integer> or Integer[] costs roughly five times what int[] does and scatters every element across the heap, and TimSort then allocates a working array on top. Switching to int[] with Arrays.sort removes both costs at once.

If the objects are genuinely objects, the next question is whether the sort is needed at all: top-k wants a bounded PriorityQueue, and a page of results wants ORDER BY ... LIMIT in the database. Reaching for parallelSort should come last — it needs O(n) more memory, not less, and on a heap-constrained service that is the wrong direction.

5. Someone proposes parallelSort everywhere because the machine has 16 cores.

It helps for large arrays and does nothing for small ones — below roughly 8,192 elements it simply calls the sequential sort. The cost is that it runs on the common ForkJoinPool, shared with every parallel stream in the JVM, so a request handler that parallel-sorts is competing with the rest of the application for the same threads.

In a service handling many concurrent requests, the cores are already busy — parallelism per request buys little and adds contention. In a batch job with one big array and idle cores, it is a real win. The deciding question is what else is running, not how many cores exist.

Interviewer's Next Move

The question after the question. This is what the round is actually testing.

1. "Which sort does Arrays.sort use?" Two answers, because there are two methods. Primitives get dual-pivot quicksort; objects get TimSort, an adaptive stable merge sort. List.sort and Collections.sort are the object path.

2. "Why are they different?" Stability. Objects that compare equal can still be distinguishable, so their relative order carries information and must be preserved. Primitives that compare equal are identical, so no program can observe the order — which means the JDK can use an in-place unstable sort and skip the O(n) working array.

3. "What does stable mean, concretely?" Equal elements keep their input order. It is what makes "sort by name, then by department" produce departments containing alphabetical names, rather than departments containing an arbitrary order.

4. "What is TimSort's complexity?" O(n log n) worst case, O(n) on already-sorted input, O(n) extra memory. The best case matters more than it sounds: real data arrives partly ordered, and TimSort finds and merges existing runs rather than starting from scratch.

5. "Can you prove which algorithm ran?" Yes — count comparator calls. A million sorted elements cost exactly n−1 comparisons, which only a run-detecting merge sort can achieve. A quicksort has to partition regardless and never learns its input was sorted.

6. "What's wrong with (a, b) -> a - b?" It overflows. Comparing a large positive against a large negative wraps the subtraction and flips the sign, so the comparator reports the wrong order. It does not throw — the array simply comes back unsorted. Use Integer.compare.

7. "Why does sorting sometimes throw about a general contract?" TimSort detected that the comparator is not a valid total order — usually subtraction overflow, or a compare returning 0 for "close enough". It is a best-effort check inside the merge step: it needs at least 32 elements to fire at all, and beyond that it depends on the data. Not throwing does not mean the comparator is correct.

8. "Can you force Arrays.sort into O(n²) with crafted input?" Not since JDK 14. DualPivotQuicksort tracks recursion depth and falls back to heap sort past a limit, so the classic quicksort-killer attack no longer applies. The concept is still worth knowing, and the specific answer about Arrays.sort is out of date.

9. "When would you not call Arrays.sort at all?" When you do not need the whole thing ordered. Top-k wants a bounded PriorityQueue at O(n log k); a median wants quickselect at O(n) average; a paged result wants the database to sort against an index. Sorting to then take ten rows is the common waste.

Code traps

Trap A — predict before you run:

List<Order> orders = ...;                       // ids from a 64-bit sequence
orders.sort((a, b) -> (int) (a.id() - b.id()));

Trap B:

Set<Version> versions = new TreeSet<>(Comparator.comparingInt(Version::major));
versions.add(new Version(2, 0));
versions.add(new Version(2, 7));
System.out.println(versions.size());

Trap C:

record Task(String name, int priority) {}
Task[] tasks = ...;
Arrays.sort(tasks, Comparator.comparingInt(Task::priority));
// later, in another thread
tasks[0] = new Task("urgent", 0);

Common wrong answers

Check Yourself

Q1. Why can Arrays.sort(int[]) be unstable when Arrays.sort(Integer[]) cannot?

Q2. A million already-sorted elements cost exactly 999,999 comparisons. What does that number prove?

Q3. Your comparator subtracts, and the sort has never thrown. Is it safe?

Practice