Java Array Sorting: Arrays.sort() and parallelSort()

Java array sorting is handled by two methods in the standard library: Arrays.sort() and Arrays.parallelSort() in the java.util package. Understanding what each method does, how ordering is determined, and when each version is appropriate matters more than memorizing syntax, because the choice affects both correctness and runtime cost.

The Core API: Arrays.sort()

The Arrays class in java.util overloads sort() for every primitive type and for object arrays. For primitives, the method sorts the array in place and returns void:

int[] numbers = { 5, 3, 8, 1, 9 };
Arrays.sort(numbers);
// numbers is now { 1, 3, 5, 8, 9 }

The array is modified directly; no copy is created. This differs from the stream-based approach, where Arrays.stream(numbers).sorted() returns a new stream of sorted elements and leaves the original array untouched. If you need to preserve the original order, copy the array before calling sort(), or use the stream approach:

int[] original = { 5, 3, 8, 1, 9 };
int[] sorted = Arrays.stream(original).sorted().toArray();

For object arrays, sort() requires that the elements implement Comparable, or you pass a Comparator as the second argument. The no-argument version throws a ClassCastException at runtime if an element does not implement Comparable.

Sorting Object Arrays with Comparators

When the natural ordering of an object does not match the ordering you need, pass a Comparator. The comparator defines the ordering without modifying the class itself:

String[] names = { "alice", "Bob", "charlie", "David" };
Arrays.sort(names, String.CASE_INSENSITIVE_ORDER);
// Result: { "alice", "Bob", "charlie", "David" } — case-insensitive alphabetical order

For custom objects, a lambda expression is the most direct way to define a comparator:

record Employee(String name, int salary) {}

Employee[] team = {
    new Employee("Alice", 85000),
    new Employee("Bob", 72000),
    new Employee("Charlie", 95000)
};

Arrays.sort(team, (a, b) -> Integer.compare(a.salary(), b.salary()));

Using Integer.compare() instead of a.salary() - b.salary() avoids integer overflow when the difference exceeds Integer.MAX_VALUE. This is a subtle but real correctness issue when numeric fields are large.

For multi-field ordering, chain comparators with Comparator.comparing() and thenComparing():

Arrays.sort(team,
    Comparator.comparing(Employee::name)
              .thenComparing(Employee::salary));

This sorts by name first, then by salary within the same name.

Implementing Comparable for Natural Ordering

When a class has a single obvious ordering, implementing Comparable makes the no-argument Arrays.sort() work directly. The compareTo method must be consistent with equals: if a.compareTo(b) == 0, then a.equals(b) should return true. Violating this contract causes subtle bugs in sorted collections and binary searches.

record Task(int priority, String title) implements Comparable<Task> {
    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}

Once Task implements Comparable, sorting an array of tasks is a single call:

Task[] tasks = { new Task(3, "Fix bug"), new Task(1, "Ship feature"), new Task(2, "Review PR") };
Arrays.sort(tasks);

The compareTo method must be transitive and antisymmetric. A common mistake is comparing only one field when the ordering should consider multiple fields. Use Comparator.comparing(...).thenComparing(...) inside compareTo to build a correct multi-field comparison.

Parallel Sorting with Arrays.parallelSort()

Arrays.parallelSort() uses the same API as sort() but splits the array into subranges, sorts them in parallel using the common ForkJoinPool, and merges the results. The overloads mirror sort() exactly, including the comparator variants.

int[] largeArray = generateLargeArray();
Arrays.parallelSort(largeArray);

Parallel sorting is not automatically faster. The overhead of splitting and merging becomes worthwhile only when the array is large — typically in the range of several thousand elements or more, depending on the hardware and the current load on the common pool. For small arrays, the sequential sort() is usually faster because the parallel setup cost exceeds the sorting time.

A second difference is that parallelSort() is stable for object arrays, while sort() uses a stable adaptive merge sort (TimSort) for objects as well. For primitives, neither version guarantees stability, because primitive values are indistinguishable when equal.

Stability and Algorithm Selection

Stability matters when the relative order of equal elements must be preserved. This is relevant when sorting an array of objects by a secondary key after it was already sorted by a primary key.

For object arrays, Arrays.sort() uses TimSort, a stable adaptive merge sort with O(n log n) worst-case time and O(n) extra space. Arrays.parallelSort() also produces stable results for object arrays.

For primitive arrays, Arrays.sort() uses a dual-pivot quicksort variant, which is not stable. Equal primitive values are indistinguishable, so stability is irrelevant for primitives. The dual-pivot quicksort runs in O(n log n) average time and O(log n) extra space.

The practical consequence: if you need to sort an object array by multiple keys and preserve the order of equal elements across passes, use Arrays.sort() with chained comparators rather than sorting the array twice. Sorting twice with a stable sort works, but a single pass with thenComparing() is clearer and avoids the extra pass.

Handling Nulls, Empty Arrays, and Edge Cases

Arrays.sort() throws NullPointerException if the array reference itself is null. An empty array or an array with a single element is sorted trivially and returns without error.

If an object array contains null elements, sort() throws NullPointerException when the comparator or compareTo encounters the null. The standard library does not provide a built-in null-safe comparator for arrays. You must handle nulls explicitly:

Arrays.sort(team, Comparator.nullsLast(
    Comparator.comparing(Employee::name)));

Comparator.nullsLast() and Comparator.nullsFirst() wrap an existing comparator and define where null elements should appear. This is the cleanest way to handle nulls without writing a custom comparator that checks for null on every comparison.

For primitive arrays, there are no null elements, so this concern does not apply.

Performance Considerations in Practice

The dominant cost of sorting is comparison, not the sort algorithm itself. For object arrays, each comparison invokes the comparator or compareTo method, which may involve field access, method calls, and boxing. Minimizing the work inside the comparator has a direct effect on total sorting time.

For primitive arrays, the dual-pivot quicksort avoids boxing entirely and operates on raw values. This is one reason sorting a primitive array is typically faster than sorting an equivalent Integer[] array.

Memory usage differs as well. TimSort allocates a temporary array of up to n/2 references for merging, while the dual-pivot quicksort uses O(log n) stack space. If memory is constrained and the array is large, this difference can matter.

The choice between sort() and parallelSort() should be based on array size and the availability of spare CPU capacity. The common ForkJoinPool is shared across the JVM, so a long-running parallel sort can delay other parallel tasks. For a batch operation on a large array, parallelSort() is reasonable. For a latency-sensitive path where other parallel work is already running, sequential sort() avoids contending for the same pool.

A final consideration: sorting in place modifies the input. If the array is shared across threads or used elsewhere after the sort, either copy it first or use the stream-based approach to produce a sorted copy. The stream approach has higher overhead but leaves the original array untouched, which is often the safer choice when the array is part of a larger data structure.