Imagine you have a massive pile of unsorted exam papers — thousands of them. You could sit down alone and sort them one by one. Or, you could divide the pile among several teaching assistants, have each sort their portion, and then merge the sorted piles back together. That second approach is exactly what Arrays.parallelSort() does.
Introduced in Java 8, Arrays.parallelSort() is a sorting method in the java.util.Arrays class that uses the Fork/Join framework to sort arrays in parallel across multiple CPU cores. Under the hood, it splits the array into sub-arrays, sorts each sub-array concurrently on separate threads, and then merges the results back together — a classic parallel merge sort.
| Feature | Arrays.sort() | Arrays.parallelSort() |
|---|---|---|
| Introduced | Java 1.2 | Java 8 |
| Thread Model | Single-threaded | Multi-threaded (Fork/Join) |
| Algorithm (primitives) | Dual-Pivot Quicksort | Parallel Merge Sort |
| Algorithm (objects) | TimSort | Parallel Merge Sort |
| Small Arrays | Optimal | Falls back to Arrays.sort() |
| Large Arrays | Slower | Significantly faster |
| API Compatibility | Same signature | Drop-in replacement |
The key insight is that parallelSort() is a drop-in replacement for Arrays.sort(). Same method signatures, same behavior, same result — just faster on large arrays with multi-core hardware.
import java.util.Arrays;
public class ParallelSortIntro {
public static void main(String[] args) {
int[] numbers = {9, 3, 7, 1, 5, 8, 2, 6, 4};
// Regular sort -- single-threaded
int[] copy1 = numbers.clone();
Arrays.sort(copy1);
System.out.println("Arrays.sort(): " + Arrays.toString(copy1));
// Output: Arrays.sort(): [1, 2, 3, 4, 5, 6, 7, 8, 9]
// Parallel sort -- multi-threaded (for large arrays)
int[] copy2 = numbers.clone();
Arrays.parallelSort(copy2);
System.out.println("Arrays.parallelSort(): " + Arrays.toString(copy2));
// Output: Arrays.parallelSort(): [1, 2, 3, 4, 5, 6, 7, 8, 9]
// Same result, different execution strategy
System.out.println("Available processors: " + Runtime.getRuntime().availableProcessors());
// Output: Available processors: 8 (varies by machine)
}
}
Arrays.parallelSort() works with all primitive array types and object arrays. The API mirrors Arrays.sort() exactly — you can swap one for the other with no other code changes.
parallelSort() is available for int[], long[], double[], float[], short[], byte[], and char[]. It sorts in natural ascending order.
import java.util.Arrays;
public class ParallelSortPrimitives {
public static void main(String[] args) {
// int array
int[] integers = {42, 17, 93, 5, 68, 31, 84, 12};
Arrays.parallelSort(integers);
System.out.println("int[]: " + Arrays.toString(integers));
// Output: int[]: [5, 12, 17, 31, 42, 68, 84, 93]
// double array
double[] doubles = {3.14, 1.41, 2.72, 0.58, 1.73};
Arrays.parallelSort(doubles);
System.out.println("double[]: " + Arrays.toString(doubles));
// Output: double[]: [0.58, 1.41, 1.73, 2.72, 3.14]
// long array
long[] longs = {100_000_000L, 50_000L, 999_999_999L, 1L};
Arrays.parallelSort(longs);
System.out.println("long[]: " + Arrays.toString(longs));
// Output: long[]: [1, 50000, 100000000, 999999999]
// char array
char[] chars = {'z', 'a', 'm', 'b', 'x'};
Arrays.parallelSort(chars);
System.out.println("char[]: " + Arrays.toString(chars));
// Output: char[]: [a, b, m, x, z]
// float array
float[] floats = {2.5f, 1.1f, 3.7f, 0.9f};
Arrays.parallelSort(floats);
System.out.println("float[]: " + Arrays.toString(floats));
// Output: float[]: [0.9, 1.1, 2.5, 3.7]
// short array
short[] shorts = {300, 100, 500, 200};
Arrays.parallelSort(shorts);
System.out.println("short[]: " + Arrays.toString(shorts));
// Output: short[]: [100, 200, 300, 500]
// byte array
byte[] bytes = {50, 10, 127, -128, 0};
Arrays.parallelSort(bytes);
System.out.println("byte[]: " + Arrays.toString(bytes));
// Output: byte[]: [-128, 0, 10, 50, 127]
}
}
String arrays are sorted in lexicographic (dictionary) order by default, since String implements Comparable<String>.
import java.util.Arrays;
public class ParallelSortStrings {
public static void main(String[] args) {
String[] languages = {"Python", "Java", "Rust", "Go", "TypeScript", "C++", "Kotlin"};
Arrays.parallelSort(languages);
System.out.println(Arrays.toString(languages));
// Output: [C++, Go, Java, Kotlin, Python, Rust, TypeScript]
// Note: uppercase letters come before lowercase in Unicode
String[] mixed = {"banana", "Apple", "cherry", "Blueberry"};
Arrays.parallelSort(mixed);
System.out.println(Arrays.toString(mixed));
// Output: [Apple, Blueberry, banana, cherry]
}
}
Any object array can be sorted with parallelSort() as long as the objects implement Comparable. If they do not, you must provide a Comparator (covered in section 4).
import java.util.Arrays;
public class ParallelSortObjects {
static class Student implements Comparable {
String name;
double gpa;
Student(String name, double gpa) {
this.name = name;
this.gpa = gpa;
}
@Override
public int compareTo(Student other) {
// Natural ordering: by GPA descending (highest first)
return Double.compare(other.gpa, this.gpa);
}
@Override
public String toString() {
return name + "(" + gpa + ")";
}
}
public static void main(String[] args) {
Student[] students = {
new Student("Alice", 3.8),
new Student("Bob", 3.5),
new Student("Charlie", 3.9),
new Student("Diana", 3.7)
};
Arrays.parallelSort(students);
System.out.println(Arrays.toString(students));
// Output: [Charlie(3.9), Alice(3.8), Diana(3.7), Bob(3.5)]
}
}
Understanding the internal mechanics of parallelSort() helps you decide when to use it and predict its behavior. The algorithm is a parallel merge sort built on top of Java’s Fork/Join framework.
The algorithm follows these steps:
Arrays.sort() — the overhead of parallelism is not worth it for small arrays.array.length / (availableProcessors << 3). On an 8-core machine with 100,000 elements, each chunk is about 1,562 elements.ForkJoinPool.commonPool().
Original Array: [9, 3, 7, 1, 5, 8, 2, 6, 4, 0]
FORK (split)
/ \
[9, 3, 7, 1, 5] [8, 2, 6, 4, 0]
/ \ / \
[9, 3, 7] [1, 5] [8, 2, 6] [4, 0]
SORT (each chunk)
[3, 7, 9] [1, 5] [2, 6, 8] [0, 4]
MERGE (join)
[1, 3, 5, 7, 9] [0, 2, 4, 6, 8]
\ /
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
| Threshold | Value | Purpose |
|---|---|---|
| MIN_ARRAY_SORT_GRAN | 8192 (0x2000) | Minimum sub-array size for parallel decomposition within the algorithm |
| Fallback threshold | 4096 or single core | Below this, parallelSort() delegates entirely to Arrays.sort() |
| Granularity formula | length / (processors << 3) | Determines how many chunks to create |
import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
public class ParallelSortInternals {
public static void main(String[] args) {
int processors = Runtime.getRuntime().availableProcessors();
System.out.println("Available processors: " + processors);
// Output: Available processors: 8 (varies)
// Show the common pool that parallelSort uses
ForkJoinPool commonPool = ForkJoinPool.commonPool();
System.out.println("Common pool parallelism: " + commonPool.getParallelism());
// Output: Common pool parallelism: 7 (processors - 1)
// Calculate granularity for different array sizes
int[] sizes = {1_000, 10_000, 100_000, 1_000_000};
for (int size : sizes) {
int granularity = size / (processors << 3);
int chunks = granularity > 0 ? size / granularity : 1;
System.out.printf("Array size: %,d -> granularity: %,d -> ~%d chunks%n",
size, granularity, chunks);
}
// Output (on 8-core machine):
// Array size: 1,000 -> granularity: 15 -> ~66 chunks
// Array size: 10,000 -> granularity: 156 -> ~64 chunks
// Array size: 100,000 -> granularity: 1,562 -> ~64 chunks
// Array size: 1,000,000 -> granularity: 15,625 -> ~64 chunks
// Demonstrate that small arrays use sequential sort internally
int[] small = new int[100];
Arrays.fill(small, 42);
long start = System.nanoTime();
Arrays.parallelSort(small); // Falls back to Arrays.sort()
long elapsed = System.nanoTime() - start;
System.out.println("Small array sort time: " + elapsed + " ns");
// Output: Small array sort time: ~1000 ns (negligible overhead)
}
}
For object arrays, parallelSort() accepts a Comparator to define custom ordering. Combined with Java 8’s lambda syntax and Comparator factory methods, this makes complex sorting logic concise and readable.
import java.util.Arrays;
import java.util.Comparator;
public class ParallelSortComparator {
public static void main(String[] args) {
String[] words = {"banana", "Apple", "cherry", "Blueberry", "avocado"};
// Default: Unicode order (uppercase before lowercase)
String[] copy1 = words.clone();
Arrays.parallelSort(copy1);
System.out.println("Default: " + Arrays.toString(copy1));
// Output: Default: [Apple, Blueberry, avocado, banana, cherry]
// Case-insensitive sort
String[] copy2 = words.clone();
Arrays.parallelSort(copy2, String.CASE_INSENSITIVE_ORDER);
System.out.println("Case-insensitive: " + Arrays.toString(copy2));
// Output: Case-insensitive: [Apple, avocado, banana, Blueberry, cherry]
// Reverse order
String[] copy3 = words.clone();
Arrays.parallelSort(copy3, Comparator.reverseOrder());
System.out.println("Reverse: " + Arrays.toString(copy3));
// Output: Reverse: [cherry, banana, avocado, Blueberry, Apple]
// Sort by length, then alphabetically
String[] copy4 = words.clone();
Arrays.parallelSort(copy4,
Comparator.comparingInt(String::length)
.thenComparing(Comparator.naturalOrder()));
System.out.println("By length then alpha: " + Arrays.toString(copy4));
// Output: By length then alpha: [Apple, banana, cherry, avocado, Blueberry]
}
}
Java 8’s Comparator.comparing() factory methods enable multi-level sorting with chained .thenComparing() calls. This is powerful with parallelSort() for sorting large datasets by multiple fields.
import java.util.Arrays;
import java.util.Comparator;
public class ParallelSortChainedComparator {
static class Employee {
String department;
String name;
double salary;
int yearsOfService;
Employee(String department, String name, double salary, int yearsOfService) {
this.department = department;
this.name = name;
this.salary = salary;
this.yearsOfService = yearsOfService;
}
@Override
public String toString() {
return String.format("%s/%s/$%.0f/%dy", department, name, salary, yearsOfService);
}
}
public static void main(String[] args) {
Employee[] employees = {
new Employee("Engineering", "Alice", 95000, 5),
new Employee("Marketing", "Bob", 75000, 3),
new Employee("Engineering", "Charlie", 105000, 8),
new Employee("Marketing", "Diana", 80000, 6),
new Employee("Engineering", "Eve", 95000, 2),
new Employee("Sales", "Frank", 70000, 4)
};
// Sort by department, then by salary descending, then by name
Arrays.parallelSort(employees,
Comparator.comparing((Employee e) -> e.department)
.thenComparing(e -> e.salary, Comparator.reverseOrder())
.thenComparing(e -> e.name));
System.out.println("Sorted by department -> salary desc -> name:");
for (Employee e : employees) {
System.out.println(" " + e);
}
// Output:
// Sorted by department -> salary desc -> name:
// Engineering/Charlie/$105000/8y
// Engineering/Alice/$95000/5y
// Engineering/Eve/$95000/2y
// Marketing/Diana/$80000/6y
// Marketing/Bob/$75000/3y
// Sales/Frank/$70000/4y
// Sort by years of service descending using method reference
Arrays.parallelSort(employees,
Comparator.comparingInt((Employee e) -> e.yearsOfService).reversed());
System.out.println("\nSorted by years of service descending:");
for (Employee e : employees) {
System.out.println(" " + e);
}
// Output:
// Sorted by years of service descending:
// Engineering/Charlie/$105000/8y
// Marketing/Diana/$80000/6y
// Engineering/Alice/$95000/5y
// Sales/Frank/$70000/4y
// Marketing/Bob/$75000/3y
// Engineering/Eve/$95000/2y
}
}
When arrays may contain null elements, use Comparator.nullsFirst() or Comparator.nullsLast() to avoid NullPointerException.
import java.util.Arrays;
import java.util.Comparator;
public class ParallelSortNullSafe {
public static void main(String[] args) {
String[] words = {"cherry", null, "apple", null, "banana"};
// nullsFirst -- nulls go to the beginning
String[] copy1 = words.clone();
Arrays.parallelSort(copy1, Comparator.nullsFirst(Comparator.naturalOrder()));
System.out.println("nullsFirst: " + Arrays.toString(copy1));
// Output: nullsFirst: [null, null, apple, banana, cherry]
// nullsLast -- nulls go to the end
String[] copy2 = words.clone();
Arrays.parallelSort(copy2, Comparator.nullsLast(Comparator.naturalOrder()));
System.out.println("nullsLast: " + Arrays.toString(copy2));
// Output: nullsLast: [apple, banana, cherry, null, null]
}
}
parallelSort() supports sorting a sub-range of an array using parallelSort(array, fromIndex, toIndex). The range is inclusive of fromIndex and exclusive of toIndex (the standard Java convention). Only the elements in the specified range are reordered; elements outside the range remain untouched.
import java.util.Arrays;
public class ParallelSortRange {
public static void main(String[] args) {
int[] numbers = {9, 3, 7, 1, 5, 8, 2, 6, 4, 0};
System.out.println("Original: " + Arrays.toString(numbers));
// Output: Original: [9, 3, 7, 1, 5, 8, 2, 6, 4, 0]
// Sort only indices 2-7 (elements: 7, 1, 5, 8, 2, 6)
Arrays.parallelSort(numbers, 2, 8);
System.out.println("Range [2,8): " + Arrays.toString(numbers));
// Output: Range [2,8): [9, 3, 1, 2, 5, 6, 7, 8, 4, 0]
// ^ ^ sorted portion ^ ^
// untouched untouched
// Sort the first 5 elements
int[] data = {50, 30, 10, 40, 20, 99, 88, 77};
Arrays.parallelSort(data, 0, 5);
System.out.println("First 5: " + Arrays.toString(data));
// Output: First 5: [10, 20, 30, 40, 50, 99, 88, 77]
// Sort the last 3 elements
int[] data2 = {50, 30, 10, 40, 20, 99, 88, 77};
Arrays.parallelSort(data2, 5, 8);
System.out.println("Last 3: " + Arrays.toString(data2));
// Output: Last 3: [50, 30, 10, 40, 20, 77, 88, 99]
// String range sort
String[] names = {"Eve", "Alice", "Diana", "Bob", "Charlie"};
Arrays.parallelSort(names, 1, 4); // Sort indices 1-3
System.out.println("Names [1,4): " + Arrays.toString(names));
// Output: Names [1,4): [Eve, Alice, Bob, Diana, Charlie]
}
}
You can combine range sorting with a comparator for object arrays:
import java.util.Arrays;
import java.util.Comparator;
public class ParallelSortRangeComparator {
public static void main(String[] args) {
Integer[] numbers = {90, 30, 70, 10, 50, 80, 20, 60};
// Sort indices 2-6 in descending order
Arrays.parallelSort(numbers, 2, 6, Comparator.reverseOrder());
System.out.println(Arrays.toString(numbers));
// Output: [90, 30, 80, 70, 50, 10, 20, 60]
// ^ ^ sorted desc ^ ^
// untouched untouched
// Invalid range throws ArrayIndexOutOfBoundsException
try {
Arrays.parallelSort(numbers, -1, 5);
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println("Error: " + e.getMessage());
// Output: Error: Array index out of range: -1
}
// fromIndex > toIndex throws IllegalArgumentException
try {
Arrays.parallelSort(numbers, 5, 2);
} catch (IllegalArgumentException e) {
System.out.println("Error: " + e.getMessage());
// Output: Error: fromIndex(5) > toIndex(2)
}
}
}
The big question: when should you use parallelSort() instead of sort()? The answer depends on array size, CPU cores, and what else your application is doing.
| Array Size | Arrays.sort() Time | Arrays.parallelSort() Time | Winner |
|---|---|---|---|
| 100 | ~1 us | ~1 us (falls back) | Tie (same code path) |
| 1,000 | ~50 us | ~60 us | sort() — overhead not justified |
| 10,000 | ~500 us | ~300 us | parallelSort() — starting to help |
| 100,000 | ~6 ms | ~2 ms | parallelSort() — 3x faster |
| 1,000,000 | ~80 ms | ~20 ms | parallelSort() — 4x faster |
| 10,000,000 | ~900 ms | ~200 ms | parallelSort() — 4-5x faster |
Note: Times are approximate and vary by hardware. Measured on an 8-core CPU with random int data.
import java.util.Arrays;
import java.util.Random;
public class SortBenchmark {
public static void main(String[] args) {
int[] sizes = {1_000, 10_000, 100_000, 1_000_000, 10_000_000};
Random random = new Random(42);
System.out.printf("%-12s %-14s %-14s %-10s%n",
"Array Size", "sort() (ms)", "parallelSort()", "Speedup");
System.out.println("-".repeat(58));
for (int size : sizes) {
// Generate random data
int[] data = random.ints(size, 0, size * 10).toArray();
// Warm up (JIT compilation)
for (int i = 0; i < 3; i++) {
Arrays.sort(data.clone());
Arrays.parallelSort(data.clone());
}
// Benchmark Arrays.sort()
long sortTotal = 0;
int runs = 5;
for (int i = 0; i < runs; i++) {
int[] copy = data.clone();
long start = System.nanoTime();
Arrays.sort(copy);
sortTotal += System.nanoTime() - start;
}
double sortMs = sortTotal / runs / 1_000_000.0;
// Benchmark Arrays.parallelSort()
long parallelTotal = 0;
for (int i = 0; i < runs; i++) {
int[] copy = data.clone();
long start = System.nanoTime();
Arrays.parallelSort(copy);
parallelTotal += System.nanoTime() - start;
}
double parallelMs = parallelTotal / runs / 1_000_000.0;
double speedup = sortMs / parallelMs;
System.out.printf("%,12d %10.2f ms %10.2f ms %8.2fx%n",
size, sortMs, parallelMs, speedup);
}
// Sample Output (8-core machine):
// Array Size sort() (ms) parallelSort() Speedup
// ----------------------------------------------------------
// 1,000 0.05 ms 0.06 ms 0.83x
// 10,000 0.52 ms 0.31 ms 1.68x
// 100,000 6.12 ms 1.89 ms 3.24x
// 1,000,000 78.45 ms 19.67 ms 3.99x
// 10,000,000 912.33 ms 198.56 ms 4.59x
}
}
Arrays.parallelPrefix() is a related parallel array method introduced in Java 8. It performs cumulative operations on an array in-place, using a given binary operator. Each element at index i is replaced with the result of applying the operator to all elements from index 0 through i.
Common use cases include running sums, running products, and running maximums.
import java.util.Arrays;
public class ParallelPrefixDemo {
public static void main(String[] args) {
// ===== Running Sum =====
int[] numbers = {1, 2, 3, 4, 5};
System.out.println("Original: " + Arrays.toString(numbers));
// Output: Original: [1, 2, 3, 4, 5]
Arrays.parallelPrefix(numbers, Integer::sum);
System.out.println("Running sum: " + Arrays.toString(numbers));
// Output: Running sum: [1, 3, 6, 10, 15]
// Explanation: [1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5]
// ===== Running Product =====
int[] factors = {1, 2, 3, 4, 5};
Arrays.parallelPrefix(factors, (a, b) -> a * b);
System.out.println("Running product: " + Arrays.toString(factors));
// Output: Running product: [1, 2, 6, 24, 120]
// These are factorials: 1!, 2!, 3!, 4!, 5!
// ===== Running Maximum =====
int[] values = {3, 1, 4, 1, 5, 9, 2, 6};
Arrays.parallelPrefix(values, Integer::max);
System.out.println("Running max: " + Arrays.toString(values));
// Output: Running max: [3, 3, 4, 4, 5, 9, 9, 9]
// ===== Running Minimum =====
int[] temps = {72, 68, 75, 65, 70, 63, 71};
Arrays.parallelPrefix(temps, Integer::min);
System.out.println("Running min: " + Arrays.toString(temps));
// Output: Running min: [72, 68, 68, 65, 65, 63, 63]
// ===== With double arrays =====
double[] prices = {10.0, 20.0, 30.0, 40.0};
Arrays.parallelPrefix(prices, Double::sum);
System.out.println("Running total: " + Arrays.toString(prices));
// Output: Running total: [10.0, 30.0, 60.0, 100.0]
// ===== Range prefix (partial) =====
int[] data = {5, 3, 8, 2, 7, 1, 9, 4};
System.out.println("Before range prefix: " + Arrays.toString(data));
Arrays.parallelPrefix(data, 2, 6, Integer::sum); // indices 2-5
System.out.println("After range [2,6): " + Arrays.toString(data));
// Output: Before range prefix: [5, 3, 8, 2, 7, 1, 9, 4]
// Output: After range [2,6): [5, 3, 8, 10, 17, 18, 9, 4]
}
}
import java.util.Arrays;
public class CumulativeRevenue {
public static void main(String[] args) {
String[] months = {"Jan", "Feb", "Mar", "Apr", "May", "Jun",
"Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
double[] monthlyRevenue = {
12_500, 15_300, 18_200, 14_800, 22_100, 19_500,
25_000, 23_400, 20_100, 28_300, 31_500, 35_200
};
// Keep a copy of original monthly values
double[] monthly = monthlyRevenue.clone();
// Calculate cumulative (year-to-date) revenue
Arrays.parallelPrefix(monthlyRevenue, Double::sum);
System.out.println("Month Monthly YTD");
System.out.println("-".repeat(35));
for (int i = 0; i < months.length; i++) {
System.out.printf("%-5s $%,10.0f $%,10.0f%n",
months[i], monthly[i], monthlyRevenue[i]);
}
// Output:
// Month Monthly YTD
// -----------------------------------
// Jan $ 12,500 $ 12,500
// Feb $ 15,300 $ 27,800
// Mar $ 18,200 $ 46,000
// Apr $ 14,800 $ 60,800
// May $ 22,100 $ 82,900
// Jun $ 19,500 $ 102,400
// Jul $ 25,000 $ 127,400
// Aug $ 23,400 $ 150,800
// Sep $ 20,100 $ 170,900
// Oct $ 28,300 $ 199,200
// Nov $ 31,500 $ 230,700
// Dec $ 35,200 $ 265,900
}
}
Arrays.parallelSetAll() fills an array by computing each element's value from its index, using a generator function. It runs in parallel, making it efficient for initializing large arrays with computed values.
The method signature is:
Arrays.parallelSetAll(array, index -> computeValue(index));
There is also a sequential version, Arrays.setAll(), which does the same thing on a single thread.
import java.util.Arrays;
public class ParallelSetAllDemo {
public static void main(String[] args) {
// ===== Fill with squares =====
int[] squares = new int[10];
Arrays.parallelSetAll(squares, i -> i * i);
System.out.println("Squares: " + Arrays.toString(squares));
// Output: Squares: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
// ===== Fill with Fibonacci-like pattern =====
long[] fib = new long[15];
fib[0] = 0;
fib[1] = 1;
// Note: parallelSetAll isn't ideal for dependent computations
// Use setAll (sequential) instead for dependencies
Arrays.setAll(fib, i -> i < 2 ? fib[i] : fib[i - 1] + fib[i - 2]);
System.out.println("Fibonacci: " + Arrays.toString(fib));
// Output: Fibonacci: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
// ===== Initialize multiplication table =====
int size = 5;
int[][] table = new int[size][size];
Arrays.parallelSetAll(table, i -> {
int[] row = new int[size];
Arrays.parallelSetAll(row, j -> (i + 1) * (j + 1));
return row;
});
System.out.println("Multiplication table:");
for (int[] row : table) {
System.out.println(" " + Arrays.toString(row));
}
// Output:
// Multiplication table:
// [1, 2, 3, 4, 5]
// [2, 4, 6, 8, 10]
// [3, 6, 9, 12, 15]
// [4, 8, 12, 16, 20]
// [5, 10, 15, 20, 25]
// ===== Generate test data (large array) =====
double[] sineWave = new double[1_000_000];
Arrays.parallelSetAll(sineWave, i -> Math.sin(2 * Math.PI * i / 1000.0));
System.out.printf("Sine wave: first=%.4f, middle=%.4f, last=%.4f%n",
sineWave[0], sineWave[500_000], sineWave[999_999]);
// Output: Sine wave: first=0.0000, middle=0.0000, last=-0.0063
// ===== Comparison: setAll vs parallelSetAll =====
int bigSize = 10_000_000;
double[] arr1 = new double[bigSize];
double[] arr2 = new double[bigSize];
long start1 = System.nanoTime();
Arrays.setAll(arr1, i -> Math.sqrt(i) * Math.log(i + 1));
long time1 = System.nanoTime() - start1;
long start2 = System.nanoTime();
Arrays.parallelSetAll(arr2, i -> Math.sqrt(i) * Math.log(i + 1));
long time2 = System.nanoTime() - start2;
System.out.printf("setAll: %d ms%n", time1 / 1_000_000);
System.out.printf("parallelSetAll: %d ms%n", time2 / 1_000_000);
System.out.printf("Speedup: %.2fx%n", (double) time1 / time2);
// Sample Output:
// setAll: 185 ms
// parallelSetAll: 52 ms
// Speedup: 3.56x
}
}
Let's measure the actual performance difference between sort() and parallelSort() across different array sizes and data patterns. This section provides empirical data to guide your decision.
The crossover point where parallelSort() becomes faster than sort() is typically around 5,000-10,000 elements, depending on hardware.
import java.util.Arrays;
import java.util.Random;
public class DetailedBenchmark {
private static final Random RANDOM = new Random(42);
public static void main(String[] args) {
System.out.println("=== Array Size Impact (random int data) ===");
System.out.println("Cores: " + Runtime.getRuntime().availableProcessors());
System.out.println();
int[] sizes = {100, 500, 1_000, 5_000, 10_000, 50_000,
100_000, 500_000, 1_000_000, 5_000_000};
System.out.printf("%-12s %-10s %-10s %-8s %-10s%n",
"Size", "sort()", "parallel()", "Speedup", "Verdict");
System.out.println("-".repeat(58));
for (int size : sizes) {
int[] data = RANDOM.ints(size).toArray();
// Warm up
for (int i = 0; i < 5; i++) {
Arrays.sort(data.clone());
Arrays.parallelSort(data.clone());
}
// Benchmark
double sortMs = benchmark(() -> Arrays.sort(data.clone()), 10);
double parallelMs = benchmark(() -> Arrays.parallelSort(data.clone()), 10);
double speedup = sortMs / parallelMs;
String verdict = speedup > 1.2 ? "PARALLEL" :
speedup < 0.8 ? "SORT" : "TIE";
System.out.printf("%,12d %7.2f ms %7.2f ms %6.2fx %-10s%n",
size, sortMs, parallelMs, speedup, verdict);
}
}
private static double benchmark(Runnable task, int iterations) {
long total = 0;
for (int i = 0; i < iterations; i++) {
long start = System.nanoTime();
task.run();
total += System.nanoTime() - start;
}
return total / iterations / 1_000_000.0;
}
// Sample Output (8-core machine):
// === Array Size Impact (random int data) ===
// Cores: 8
//
// Size sort() parallel() Speedup Verdict
// ----------------------------------------------------------
// 100 0.00 ms 0.00 ms 1.00x TIE
// 500 0.02 ms 0.02 ms 1.00x TIE
// 1,000 0.04 ms 0.05 ms 0.80x TIE
// 5,000 0.25 ms 0.18 ms 1.39x PARALLEL
// 10,000 0.55 ms 0.30 ms 1.83x PARALLEL
// 50,000 3.10 ms 1.12 ms 2.77x PARALLEL
// 100,000 6.50 ms 2.05 ms 3.17x PARALLEL
// 500,000 37.20 ms 10.30 ms 3.61x PARALLEL
// 1,000,000 78.00 ms 20.50 ms 3.80x PARALLEL
// 5,000,000 420.00 ms 98.00 ms 4.29x PARALLEL
}
The initial ordering of data affects how much benefit you get from parallel sorting:
| Data Pattern | sort() Behavior | parallelSort() Behavior | Winner |
|---|---|---|---|
| Random | Full work | Full parallel work | parallelSort() for large arrays |
| Already sorted | Very fast (TimSort optimized) | Still splits and merges | sort() -- adaptive wins |
| Reverse sorted | Moderate (TimSort handles) | Full parallel work | parallelSort() for large arrays |
| Nearly sorted | Very fast (few corrections) | Still splits and merges | sort() -- fewer operations |
| Many duplicates | Moderate | Parallel helps | parallelSort() for large arrays |
import java.util.Arrays;
import java.util.Random;
public class DataPatternBenchmark {
private static final int SIZE = 1_000_000;
private static final Random RANDOM = new Random(42);
public static void main(String[] args) {
System.out.println("=== Data Pattern Impact (1,000,000 elements) ===\n");
// Random data
int[] random = RANDOM.ints(SIZE).toArray();
benchmarkPattern("Random", random);
// Already sorted
int[] sorted = random.clone();
Arrays.sort(sorted);
benchmarkPattern("Already sorted", sorted);
// Reverse sorted
int[] reversed = new int[SIZE];
for (int i = 0; i < SIZE; i++) reversed[i] = SIZE - i;
benchmarkPattern("Reverse sorted", reversed);
// Nearly sorted (5% elements displaced)
int[] nearlySorted = sorted.clone();
for (int i = 0; i < SIZE / 20; i++) {
int a = RANDOM.nextInt(SIZE);
int b = RANDOM.nextInt(SIZE);
int temp = nearlySorted[a];
nearlySorted[a] = nearlySorted[b];
nearlySorted[b] = temp;
}
benchmarkPattern("Nearly sorted", nearlySorted);
// All same value
int[] allSame = new int[SIZE];
Arrays.fill(allSame, 42);
benchmarkPattern("All same value", allSame);
}
private static void benchmarkPattern(String name, int[] data) {
// Warm up
for (int i = 0; i < 3; i++) {
Arrays.sort(data.clone());
Arrays.parallelSort(data.clone());
}
long sortTotal = 0, parallelTotal = 0;
int runs = 5;
for (int i = 0; i < runs; i++) {
long start = System.nanoTime();
Arrays.sort(data.clone());
sortTotal += System.nanoTime() - start;
start = System.nanoTime();
Arrays.parallelSort(data.clone());
parallelTotal += System.nanoTime() - start;
}
double sortMs = sortTotal / runs / 1_000_000.0;
double parallelMs = parallelTotal / runs / 1_000_000.0;
System.out.printf("%-16s sort: %7.1f ms parallel: %7.1f ms speedup: %.2fx%n",
name, sortMs, parallelMs, sortMs / parallelMs);
}
// Sample Output:
// === Data Pattern Impact (1,000,000 elements) ===
//
// Random sort: 78.5 ms parallel: 20.1 ms speedup: 3.90x
// Already sorted sort: 5.2 ms parallel: 8.3 ms speedup: 0.63x
// Reverse sorted sort: 7.1 ms parallel: 12.5 ms speedup: 0.57x
// Nearly sorted sort: 12.3 ms parallel: 14.8 ms speedup: 0.83x
// All same value sort: 3.1 ms parallel: 6.7 ms speedup: 0.46x
}
parallelSort() uses the ForkJoinPool.commonPool() to execute its parallel tasks. This has important implications for thread safety and resource sharing.
The common pool is a JVM-wide shared thread pool. All parallel operations that do not specify a custom pool -- including parallelSort(), parallel streams, and CompletableFuture.supplyAsync() -- compete for the same threads.
| Property | Detail |
|---|---|
| Default parallelism | Runtime.getRuntime().availableProcessors() - 1 |
| Shared by | parallelSort, parallel streams, CompletableFuture (default) |
| Override | -Djava.util.concurrent.ForkJoinPool.common.parallelism=N |
| Thread type | Daemon threads (do not prevent JVM shutdown) |
Your Comparator must be thread-safe because parallelSort() invokes it from multiple threads simultaneously. This means:
compare(a, b) must always return the same value for the same inputsa > b and b > c, then a > cimport java.util.Arrays;
import java.util.Comparator;
public class ThreadSafetyConsiderations {
// ===== BAD: Stateful comparator with shared mutable state =====
static int comparisonCount = 0; // NOT thread-safe!
static Comparator badComparator = (a, b) -> {
comparisonCount++; // Race condition! Multiple threads modify this
return Integer.compare(a, b);
};
// ===== GOOD: Stateless comparator =====
static Comparator goodComparator = Integer::compare;
// ===== GOOD: Thread-safe counting with AtomicInteger =====
static final java.util.concurrent.atomic.AtomicInteger safeCount =
new java.util.concurrent.atomic.AtomicInteger(0);
static Comparator safeCountingComparator = (a, b) -> {
safeCount.incrementAndGet(); // Thread-safe
return Integer.compare(a, b);
};
public static void main(String[] args) {
Integer[] data = new Integer[100_000];
Arrays.parallelSetAll(data, i -> (int)(Math.random() * 100_000));
// Using the safe comparator
safeCount.set(0);
Arrays.parallelSort(data.clone(), safeCountingComparator);
System.out.println("Comparisons made: " + safeCount.get());
// Output: Comparisons made: ~1,600,000 (varies)
// Comparable contract: compareTo must be consistent with equals
System.out.println("\n--- Comparable Contract ---");
String[] words = {"apple", "APPLE", "Apple"};
Arrays.parallelSort(words); // Uses String.compareTo (case-sensitive)
System.out.println("Case-sensitive: " + Arrays.toString(words));
// Output: Case-sensitive: [APPLE, Apple, apple]
Arrays.parallelSort(words, String.CASE_INSENSITIVE_ORDER);
System.out.println("Case-insensitive: " + Arrays.toString(words));
// Output: Case-insensitive: [APPLE, Apple, apple]
}
}
Even though parallelSort() is a drop-in replacement for sort(), there are pitfalls that can negate its benefits or introduce bugs.
For arrays under ~5,000 elements, parallelSort() has no advantage. It internally falls back to Arrays.sort() for very small arrays, but there is still minor overhead from the method dispatch. Do not optimize prematurely.
Because parallelSort() calls your comparator from multiple threads, any side effects create race conditions:
import java.util.Arrays;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.List;
public class CommonMistakes {
public static void main(String[] args) {
// ===== Mistake: Collecting during comparison =====
List log = new ArrayList<>(); // NOT thread-safe!
String[] names = {"Charlie", "Alice", "Bob", "Diana", "Eve"};
// BAD: Writing to shared ArrayList from comparator
// Arrays.parallelSort(names, (a, b) -> {
// log.add(a + " vs " + b); // ConcurrentModificationException possible!
// return a.compareTo(b);
// });
// GOOD: Use a thread-safe collection if you must log
List safeLog = java.util.Collections.synchronizedList(new ArrayList<>());
Arrays.parallelSort(names, (a, b) -> {
safeLog.add(a + " vs " + b);
return a.compareTo(b);
});
System.out.println("Comparisons: " + safeLog.size());
// Output: Comparisons: 7 (for 5-element array)
// ===== Mistake: Non-Comparable objects without Comparator =====
// This class does NOT implement Comparable
class Product {
String name;
double price;
Product(String n, double p) { name = n; price = p; }
}
Product[] products = {
new Product("Widget", 9.99),
new Product("Gadget", 24.99),
new Product("Doohickey", 4.99)
};
// BAD: ClassCastException at runtime
// Arrays.parallelSort(products);
// GOOD: Provide a Comparator
Arrays.parallelSort(products, Comparator.comparingDouble(p -> p.price));
for (Product p : products) {
System.out.println(p.name + ": $" + p.price);
}
// Output:
// Doohickey: $4.99
// Widget: $9.99
// Gadget: $24.99
// ===== Mistake: Inconsistent Comparator =====
// A comparator that violates the contract can cause unpredictable results
Integer[] nums = {3, 1, 4, 1, 5, 9, 2, 6};
// BAD: Not transitive (random results each time)
// Comparator broken = (a, b) -> (int)(Math.random() * 3) - 1;
// Arrays.parallelSort(nums, broken); // IllegalArgumentException possible!
// GOOD: Consistent comparator
Arrays.parallelSort(nums, Integer::compare);
System.out.println("Sorted: " + Arrays.toString(nums));
// Output: Sorted: [1, 1, 2, 3, 4, 5, 6, 9]
}
}
Like Arrays.sort(), parallelSort() sorts the array in place. If you need to preserve the original order, clone the array first.
import java.util.Arrays;
public class InPlaceMistake {
public static void main(String[] args) {
int[] original = {5, 3, 8, 1, 9, 2};
// BAD: Original array is modified
// Arrays.parallelSort(original);
// System.out.println(Arrays.toString(original)); // [1, 2, 3, 5, 8, 9] -- original gone!
// GOOD: Sort a copy
int[] sorted = original.clone();
Arrays.parallelSort(sorted);
System.out.println("Original: " + Arrays.toString(original));
System.out.println("Sorted: " + Arrays.toString(sorted));
// Output:
// Original: [5, 3, 8, 1, 9, 2]
// Sorted: [1, 2, 3, 5, 8, 9]
}
}
If your application already uses parallel streams or CompletableFuture heavily, adding parallelSort() creates contention for the shared common pool. In CPU-bound applications, this can actually slow things down.
Arrays.parallelSort() for object arrays is a stable sort (equal elements maintain their relative order). However, for primitive arrays, stability is meaningless since there is no concept of "identity" for equal primitive values. Be aware that the object version guarantees stability, which matters when sorting by one field after another.
Follow these guidelines to get the most out of Java 8's parallel array operations.
| # | Do | Don't |
|---|---|---|
| 1 | Use parallelSort() for arrays with 10,000+ elements |
Don't use it for small arrays -- overhead exceeds benefit |
| 2 | Keep comparators stateless and side-effect-free | Don't write to shared mutable state in comparators |
| 3 | Clone the array if you need the original order preserved | Don't forget that parallelSort modifies in-place |
| 4 | Use Comparator.comparing() chains for multi-field sorting |
Don't write manual comparison logic with subtraction |
| 5 | Benchmark with your actual data before switching | Don't assume parallel is always faster |
| 6 | Use parallelSetAll() to initialize large arrays |
Don't use it for arrays with element dependencies |
| 7 | Use parallelPrefix() for cumulative operations |
Don't use non-associative operators with parallelPrefix |
| 8 | Consider the common pool's capacity before using parallel ops | Don't combine many parallel operations without considering pool contention |
| 9 | Use Comparator.nullsFirst()/nullsLast() for nullable arrays |
Don't let NullPointerException crash your comparator |
| 10 | Profile on the target deployment hardware | Don't benchmark on a dev laptop and assume production results |
Is the array size > 10,000?
├── NO --> Use Arrays.sort()
└── YES --> Is the data mostly sorted?
├── YES --> Use Arrays.sort() (adaptive algorithms win)
└── NO --> Is your app CPU-bound with heavy parallel workloads?
├── YES --> Benchmark both; common pool contention may hurt
└── NO --> Use Arrays.parallelSort()
This example simulates a real-world scenario: sorting a large dataset of sales transactions and computing analytics. It demonstrates parallelSort(), parallelSetAll(), parallelPrefix(), range sorting, and custom comparators -- all benchmarked against their sequential counterparts.
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class SalesAnalytics {
static class Transaction implements Comparable {
final int id;
final String region;
final String product;
final double amount;
final long timestamp;
Transaction(int id, String region, String product, double amount, long timestamp) {
this.id = id;
this.region = region;
this.product = product;
this.amount = amount;
this.timestamp = timestamp;
}
@Override
public int compareTo(Transaction other) {
return Double.compare(this.amount, other.amount);
}
@Override
public String toString() {
return String.format("TX#%d[%s/%s/$%.2f]", id, region, product, amount);
}
}
private static final String[] REGIONS = {"North", "South", "East", "West", "Central"};
private static final String[] PRODUCTS = {"Widget", "Gadget", "Doohickey", "Thingamajig", "Whatchamacallit"};
public static void main(String[] args) {
int datasetSize = 500_000;
Random random = new Random(42);
// ===== 1. Generate large dataset with parallelSetAll =====
System.out.println("=== Sales Analytics System ===");
System.out.println("Dataset size: " + String.format("%,d", datasetSize) + " transactions\n");
Transaction[] transactions = new Transaction[datasetSize];
long genStart = System.nanoTime();
Arrays.parallelSetAll(transactions, i -> new Transaction(
i + 1,
REGIONS[Math.abs(hash(i, 1)) % REGIONS.length],
PRODUCTS[Math.abs(hash(i, 2)) % PRODUCTS.length],
10.0 + (hash(i, 3) & 0x7FFFFFFF) % 99000 / 100.0,
System.currentTimeMillis() - (long)(Math.abs(hash(i, 4)) % 86_400_000)
));
long genTime = System.nanoTime() - genStart;
System.out.printf("Data generation (parallelSetAll): %d ms%n%n", genTime / 1_000_000);
// ===== 2. Sort by amount -- sequential vs parallel =====
Transaction[] seqCopy = transactions.clone();
long seqStart = System.nanoTime();
Arrays.sort(seqCopy);
long seqTime = System.nanoTime() - seqStart;
Transaction[] parCopy = transactions.clone();
long parStart = System.nanoTime();
Arrays.parallelSort(parCopy);
long parTime = System.nanoTime() - parStart;
System.out.println("--- Sort by Amount (natural order) ---");
System.out.printf("Sequential sort: %d ms%n", seqTime / 1_000_000);
System.out.printf("Parallel sort: %d ms%n", parTime / 1_000_000);
System.out.printf("Speedup: %.2fx%n%n", (double) seqTime / parTime);
// ===== 3. Multi-field sort with Comparator chains =====
Transaction[] multiSort = transactions.clone();
Comparator multiComparator =
Comparator.comparing((Transaction t) -> t.region)
.thenComparing(t -> t.product)
.thenComparing(Comparator.comparingDouble((Transaction t) -> t.amount).reversed());
long multiStart = System.nanoTime();
Arrays.parallelSort(multiSort, multiComparator);
long multiTime = System.nanoTime() - multiStart;
System.out.println("--- Multi-field Sort (region -> product -> amount desc) ---");
System.out.printf("Parallel sort time: %d ms%n", multiTime / 1_000_000);
System.out.println("First 5:");
for (int i = 0; i < 5; i++) System.out.println(" " + multiSort[i]);
System.out.println("Last 5:");
for (int i = datasetSize - 5; i < datasetSize; i++) System.out.println(" " + multiSort[i]);
System.out.println();
// ===== 4. Extract amounts and compute running total with parallelPrefix =====
double[] amounts = new double[datasetSize];
Arrays.parallelSetAll(amounts, i -> parCopy[i].amount); // sorted amounts
double[] cumulative = amounts.clone();
long prefixStart = System.nanoTime();
Arrays.parallelPrefix(cumulative, Double::sum);
long prefixTime = System.nanoTime() - prefixStart;
System.out.println("--- Cumulative Revenue (parallelPrefix) ---");
System.out.printf("parallelPrefix time: %d ms%n", prefixTime / 1_000_000);
System.out.printf("Total revenue: $%,.2f%n", cumulative[cumulative.length - 1]);
System.out.printf("Median transaction: $%,.2f%n", amounts[amounts.length / 2]);
System.out.printf("Lowest: $%,.2f | Highest: $%,.2f%n%n", amounts[0], amounts[amounts.length - 1]);
// ===== 5. Top 10 transactions (range sort) =====
Transaction[] topTen = transactions.clone();
// Sort only the last 10 positions in descending order
Arrays.parallelSort(topTen, Comparator.comparingDouble((Transaction t) -> t.amount).reversed());
System.out.println("--- Top 10 Transactions ---");
for (int i = 0; i < 10; i++) {
System.out.printf(" #%d: %s%n", i + 1, topTen[i]);
}
// ===== Summary =====
System.out.println("\n--- Performance Summary ---");
System.out.println("Operation Time");
System.out.println("-".repeat(50));
System.out.printf("Data generation (parallelSetAll) %d ms%n", genTime / 1_000_000);
System.out.printf("Sequential sort %d ms%n", seqTime / 1_000_000);
System.out.printf("Parallel sort %d ms%n", parTime / 1_000_000);
System.out.printf("Multi-field parallel sort %d ms%n", multiTime / 1_000_000);
System.out.printf("Cumulative sum (parallelPrefix) %d ms%n", prefixTime / 1_000_000);
}
// Simple deterministic hash for reproducible test data
private static int hash(int value, int seed) {
int h = value * 0x9E3779B9 + seed;
h ^= h >>> 16;
h *= 0x85EBCA6B;
h ^= h >>> 13;
return h;
}
// Sample Output (8-core machine):
// === Sales Analytics System ===
// Dataset size: 500,000 transactions
//
// Data generation (parallelSetAll): 45 ms
//
// --- Sort by Amount (natural order) ---
// Sequential sort: 312 ms
// Parallel sort: 89 ms
// Speedup: 3.51x
//
// --- Multi-field Sort (region -> product -> amount desc) ---
// Parallel sort time: 156 ms
// First 5:
// TX#482312[Central/Doohickey/$999.90]
// TX#311204[Central/Doohickey/$998.50]
// TX#91826[Central/Doohickey/$997.30]
// TX#228445[Central/Doohickey/$996.80]
// TX#405632[Central/Doohickey/$995.20]
// Last 5:
// TX#174523[West/Widget/$12.40]
// TX#389201[West/Widget/$11.90]
// TX#23456[West/Widget/$11.20]
// TX#256789[West/Widget/$10.80]
// TX#445123[West/Widget/$10.10]
//
// --- Cumulative Revenue (parallelPrefix) ---
// parallelPrefix time: 12 ms
// Total revenue: $249,875,312.50
// Median transaction: $505.00
// Lowest: $10.00 | Highest: $1,000.00
//
// --- Top 10 Transactions ---
// #1: TX#142857[North/Gadget/$999.99]
// #2: TX#482312[Central/Doohickey/$999.90]
// ...
//
// --- Performance Summary ---
// Operation Time
// --------------------------------------------------
// Data generation (parallelSetAll) 45 ms
// Sequential sort 312 ms
// Parallel sort 89 ms
// Multi-field parallel sort 156 ms
// Cumulative sum (parallelPrefix) 12 ms
}
All parallel array methods introduced in Java 8, at a glance:
| Method | Description | Supported Types |
|---|---|---|
parallelSort(T[]) |
Sort entire array in parallel (natural order) | All primitives + Comparable objects |
parallelSort(T[], Comparator) |
Sort entire array with custom comparator | Object arrays |
parallelSort(T[], from, to) |
Sort range [from, to) in parallel | All primitives + Comparable objects |
parallelSort(T[], from, to, Comparator) |
Sort range with custom comparator | Object arrays |
parallelPrefix(T[], BinaryOperator) |
Cumulative operation across entire array | int[], long[], double[], T[] |
parallelPrefix(T[], from, to, BinaryOperator) |
Cumulative operation on range [from, to) | int[], long[], double[], T[] |
parallelSetAll(T[], IntFunction) |
Set each element using index-based generator | int[], long[], double[], T[] |
setAll(T[], IntFunction) |
Sequential version of parallelSetAll | int[], long[], double[], T[] |
| Scenario | Recommended Method | Why |
|---|---|---|
| Small array (< 5,000 elements) | Arrays.sort() |
No parallel benefit, avoid overhead |
| Large array (> 10,000 elements, random) | Arrays.parallelSort() |
3-5x faster on multi-core |
| Already-sorted or nearly-sorted data | Arrays.sort() |
TimSort's adaptive algorithm excels |
| Initialize large array with computed values | Arrays.parallelSetAll() |
Parallel computation per index |
| Running sum/max/min across array | Arrays.parallelPrefix() |
Parallel cumulative operation |
| CPU-bound app with heavy ForkJoin usage | Arrays.sort() |
Avoid common pool contention |
| Sorting with nullable elements | parallelSort(arr, nullsFirst(...)) |
Null-safe with Comparator factory |
Key takeaway: Arrays.parallelSort() is a powerful tool in the Java 8 toolbox, but it is not a silver bullet. Use it for large arrays with random data on multi-core hardware, and always benchmark with your actual dataset. For small arrays or already-sorted data, stick with Arrays.sort().