Array Parallel Sort

Arrays.parallelSort sorts an array using every core on the machine instead of one. It is a single-word change from Arrays.sort, which makes it tempting to use everywhere — and it is slower than the sequential version on most of the arrays you will actually sort.

Using it

class Demo {
    void run() {
        int[] numbers = {5, 2, 9, 1, 7};
        Arrays.parallelSort(numbers);
        System.out.println(Arrays.toString(numbers));    // [1, 2, 5, 7, 9]

        String[] names = {"Cy", "Ana", "Bo"};
        Arrays.parallelSort(names);
        System.out.println(Arrays.toString(names));      // [Ana, Bo, Cy]
    }
}

Like Arrays.sort, it sorts in place and returns void. Writing int[] sorted = Arrays.parallelSort(numbers); does not compile, which is a common first mistake.

How it works

It is a parallel merge sort built on the fork/join framework. The array is split in half repeatedly until each piece is small enough to be worth sorting directly, those pieces are sorted on separate threads, and the results are merged back up.

Two consequences follow from that description, and both matter more than the algorithm itself:

• It needs a working array as large as the one you gave it. The merge step cannot be done in place, so sorting a 100 MB array allocates another 100 MB.
• Below a threshold it does not parallelise at all. The JDK sets that cutoff at 8,192 elements; under it, parallelSort simply calls the sequential sort. So on a small array the two methods are identical apart from one extra check.

Comparators and ranges

record Person(String name, int age) { }

class Demo {
    void run() {
        Person[] people = {
                new Person("Cy", 35),
                new Person("Ana", 30),
                new Person("Bo", 25)};

        Arrays.parallelSort(people, Comparator.comparingInt(Person::age));
        System.out.println(people[0].name());            // Bo

        // Sort only part of an array — from inclusive, to exclusive
        int[] numbers = {9, 8, 7, 3, 1, 2};
        Arrays.parallelSort(numbers, 3, 6);
        System.out.println(Arrays.toString(numbers));    // [9, 8, 7, 1, 2, 3]
    }
}

The comparator overload only exists for object arrays. Primitive arrays sort in natural order and there is no way to supply a comparator — if you need one, box to Integer[], at which point you have probably lost whatever performance you were chasing.

When it is actually faster

Three conditions have to hold together, and if any one fails the sequential sort wins:

The condition people forget is the second. parallelSort uses the common ForkJoinPool, which is shared by every parallel stream in the JVM. Inside a web application handling concurrent requests, all your cores are already busy and there is nothing to parallelise into — you have added coordination overhead to a sort that was fine.

Measure it, do not assume

class Benchmark {
    void compare(int size) {
        int[] a = new int[size];
        Random random = new Random(42);              // fixed seed: same data both times
        for (int i = 0; i < size; i++) {
            a[i] = random.nextInt();
        }
        int[] b = Arrays.copyOf(a, a.length);

        long t0 = System.nanoTime();
        Arrays.sort(a);
        long sequential = System.nanoTime() - t0;

        long t1 = System.nanoTime();
        Arrays.parallelSort(b);
        long parallel = System.nanoTime() - t1;

        System.out.println(size + ": sequential " + sequential / 1_000_000 + "ms, "
                + "parallel " + parallel / 1_000_000 + "ms");
    }
}

Run that across a range of sizes on the machine that will run the code, and you will find the crossover point. It is usually somewhere in the tens of thousands, and it moves with the hardware — which is the real argument for measuring rather than memorising a number from a blog post.

Note the fixed Random seed. Sorting is sensitive to the data: an already-sorted array behaves completely differently from a random one, so both runs must see the same input for the comparison to mean anything.

The other parallel array methods

class Demo {
    void run() {
        // Fill an array from its index, in parallel
        int[] squares = new int[10];
        Arrays.parallelSetAll(squares, i -> i * i);
        System.out.println(Arrays.toString(squares));   // [0, 1, 4, 9, 16, ...]

        // Running totals, in place
        int[] values = {1, 2, 3, 4};
        Arrays.parallelPrefix(values, Integer::sum);
        System.out.println(Arrays.toString(values));    // [1, 3, 6, 10]
    }
}

parallelPrefix is the unusual one — it turns an array into its running totals, and the operation you pass must be associative, because the pieces are combined in an unspecified order. Integer::sum is; subtraction is not, and passing it produces wrong answers rather than an error.

Thread safety

One thing the method does not do is make the array safe to touch while it is being sorted. The sort is parallel internally, but the array is still yours and nothing guards it:

If another thread reads the array during a parallelSort, it sees a half-sorted state — not a stale snapshot, an inconsistent one. If another thread writes to it, the result is undefined and may not even be a permutation of what you started with. The same is true of Arrays.sort, but a parallel sort widens the window and makes the race far easier to hit.

The fix is the ordinary one: do not share a mutable array across threads. Sort it before you publish it, or copy it first with Arrays.copyOf and sort the copy.

The rule

Use Arrays.sort. Reach for parallelSort only when you have a large array, a machine with cores to spare, and a measurement showing it helps. The single-word change is seductive precisely because it hides all three conditions.

Next

CompletableFuture is next — running work off the calling thread deliberately, rather than hoping a library does it for you.