parallelSort, parallelPrefix, parallelSetAll?

• parallelSort – parallel merge sort; splits, sorts chunks on threads, merges; sequential below ~8192 elements.
• parallelPrefix – running cumulative operation (prefix scan) in parallel across the array.
• parallelSetAll – fills each element from its index using a generator function in parallel.
• Common ForkJoinPool – shared process-wide, default parallelism = available processors minus 1.
• Threshold – all three fall back to sequential for small arrays; parallel overhead > work saved.

How does parallelSort work?

Arrays.parallelSort uses a parallel merge sort. It splits the array into chunks, sorts each chunk on a separate thread from the common ForkJoinPool, and merges the sorted chunks.

package com.bank.parallel;

import java.math.BigDecimal;
import java.util.Arrays;

public class ParallelSortDemo {
    public static void main(String[] args) {
        BigDecimal[] amounts = new BigDecimal[1_000_000];
        for (int i = 0; i < amounts.length; i++) {
            amounts[i] = BigDecimal.valueOf(Math.random() * 100000);
        }
        Arrays.parallelSort(amounts);  // parallel merge sort on common ForkJoinPool
        System.out.println("Smallest: " + amounts[0]);
        System.out.println("Largest: " + amounts[amounts.length - 1]);
    }
}

Internally it goes parallel above approximately 8192 elements. Below that threshold, it calls sequential Arrays.sort, which uses a dual-pivot quicksort for primitives and TimSort for objects.

How does parallelPrefix work?

parallelPrefix computes a running cumulative operation across the array. After the call, each element at index i contains the cumulative result of applying the operator from index 0 through i.

package com.bank.parallel;

import java.math.BigDecimal;
import java.util.Arrays;

public class ParallelPrefixDemo {
    public static void main(String[] args) {
        BigDecimal[] dailyNet = {
            new BigDecimal("10000"),
            new BigDecimal("-2500"),
            new BigDecimal("5000"),
            new BigDecimal("-1000"),
            new BigDecimal("3000")
        };
        Arrays.parallelPrefix(dailyNet, BigDecimal::add);
        // dailyNet is now: [10000, 7500, 12500, 11500, 14500]
        // dailyNet[i] is the cumulative balance through day i
        System.out.println("Day 5 cumulative balance: " + dailyNet[4]);
    }
}

How does parallelSetAll work?

parallelSetAll fills each element from its index using a generator function, computed in parallel.

package com.bank.parallel;

import java.math.BigDecimal;
import java.util.Arrays;

public class ParallelSetAllDemo {
    public static void main(String[] args) {
        BigDecimal[] fees = new BigDecimal[1000];
        BigDecimal baseFee = new BigDecimal("10.00");
        BigDecimal step = new BigDecimal("0.50");
        Arrays.parallelSetAll(fees,
            i -> baseFee.add(step.multiply(BigDecimal.valueOf(i))));
        // fees[0] = 10.00, fees[1] = 10.50, fees[999] = 509.50
        System.out.println("Fee at index 999: " + fees[999]);
    }
}

What is the common ForkJoinPool concern?

All three methods share the common pool with parallel streams and default CompletableFutures. A long parallel sort on a million elements can delay other parallel work in the same JVM process. Do not mix blocking IO into anything sharing the common pool.

When does parallel actually pay off?

| Condition | Parallel Helps? | Reason |
|-----------|----------------|--------|
| Large array (10K+ elements) | Yes | Enough work to amortize overhead |
| Multi-core machine (4+ cores) | Yes | Actual parallelism available |
| Non-trivial per-element cost | Yes | More work per element means more benefit |
| Small array (less than 1K) | No | Overhead dominates actual work |
| Single-core machine | No | No parallelism, only overhead |
| Cheap comparison (int sort) | Maybe not | Comparison cost too low to offset fork/join overhead |

How do you benchmark parallel vs sequential?

Use JMH to measure accurately. JVM warm-up, JIT compilation, and garbage collection can mislead naive benchmarks.

@Benchmark
public void sequentialSort(Blackhole bh) {
    BigDecimal[] copy = amounts.clone();
    Arrays.sort(copy);
    bh.consume(copy);
}

@Benchmark
public void parallelSort(Blackhole bh) {
    BigDecimal[] copy = amounts.clone();
    Arrays.parallelSort(copy);
    bh.consume(copy);
}

What are common mistakes?

Using parallelSort on small arrays adds overhead without benefit. Another mistake is assuming parallelPrefix produces the same result as a sequential loop when the operator is not associative. The operator must be associative (order of grouping does not matter) for parallel prefix to produce correct results.

What are common interview follow-up questions?

• How do you change the common ForkJoinPool parallelism? Set the system property -Djava.util.concurrent.ForkJoinPool.common.parallelism=N.
• Can you run parallelSort on a custom ForkJoinPool? Not directly. The API always uses the common pool. You can submit the entire sort as a task to a custom pool.
• How does parallelPrefix implement the parallel scan algorithm? It uses a two-pass approach: an up-sweep (reduce) to compute subtotals, then a down-sweep to propagate the cumulative result.